T-SQL Pbdfk2 (Rfc2898 SHA2_256) Implementation

Question

Using my previous function as a base I've come up the following:

create function dbo.Pbkdf2 (
 @password varbinary(8000)
 , @salt varbinary(7996)
 , @iterations int = 1000
 , @derivedKeyLength int = 32
)
returns varbinary(max)
as
begin; 
 declare @hmacLength int = 32; 
 declare @i int = 1;
 declare @l int = (@derivedKeyLength + @hmacLength - 1) / @hmacLength;
 declare @r int = @derivedKeyLength - (@l - 1) * @hmacLength; 
 declare @derivedKey varbinary(max) = Cast('' as varbinary(max));
 declare @u varbinary(8000);
 declare @uA binary(32);
 declare @uB binary(32); 
 while(@i <= @l)
 begin;
 declare @j int = 1;
 select @u = @salt + Cast(@i as binary(4)); 
 select @uA = uA.[Hash]
 , @uB = uA.[Hash]
 from dbo.Hmac(@password, @u) as uA;
 while @j < @iterations
 begin;
 select @uA = tA.[Hash] from dbo.Hmac(@password, @uA) as tA;
 select @uB = tB.[Hash]
 from (values(
 -- unrolled loop to XOR uA and uB
 Cast(Substring(@uA, 1, 8) ^ Cast(Substring(@uB, 1, 8) as bigint) as binary(8))
 + Cast(Substring(@uA, 9, 8) ^ Cast(Substring(@uB, 9, 8) as bigint) as binary(8))
 + Cast(Substring(@uA, 17, 8) ^ Cast(Substring(@uB, 17, 8) as bigint) as binary(8))
 + Cast(Substring(@uA, 25, 8) ^ Cast(Substring(@uB, 25, 8) as bigint) as binary(8))
 )) tB ([Hash]);
 select @j = @j + 1;
 end;
 select @derivedKey = @derivedKey + Cast(case when @i = @l then Left(@uB, @r) else @uB end as varbinary(32));
 select @i = @i + 1;
 end;
 return @derivedKey;
end;

I'd really like to replace the loops with something set-based so that I can turn this into an inline-TVF but just can't seem to wrap my head around it...

• Caridorc: Please, avoid posting many questions in a row. Post one, wait until you get an answer, wait a day, and post another one
• Kittoes0124: @Caridorc I didn't, I merely added a reference to the actual spec in the title of 2 other existing posts when creating this one because I believed it added clarity.
• Caridorc: Sure you did well, my bad, I did not look carefully enough at the main page... Hope you get some nice answers.

Answer 1

I took a very, very wild swing at this. I also couldn't get it down to something entirely set-based, but I was able to get it to an inline TVF with a recursive CTE (two of them, unfortunately). With 1000 iterations, I needed a MAXRECURSION of at least 998 to get it to finish.

I wouldn't trust this as a cryptographically secure implementation. I strongly suspect that the optimizer could do something funny here that would enable timing attacks; likely some very aggressive query hinting would be needed to ensure a stable join order and methodology. With some digging, I think we would have to do the following (at a minimum) to make it cryptographically secure. All of these are to prevent timing attacks:

1. Force LOOP joins; HASH joins use hash tables, which have known timing attack vulnerabilities, and MERGE joins will sort, which will be impacted by the available data.
2. Force a join order (OPTION( FORCE ORDER )); if the optimizer knows something about the cardinality of the data set and re-orders as a result we'll also see different numbers.
3. Disable parallelism (OPTION( MAXDOP 1 ))

Throughout all of this I'm heavily relying on the behavior of the APPLY operator where it evaluates the right-hand side for each row of the left-hand side. This was vital to get some of these complicated calculations, and I suspect is the path towards a non-recursive implementation (if there is one).

The first thing I had to do was re-create your outer loop calculations, which I did with something like this. You might need more in the counter in the middle (just keep CROSS APPLYing to sys.all_objects), but this was fine for my test cases.

SELECT uAOuter.Hash UA,
 uAOuter.Hash UB,
 OuterLooper.Counter
 FROM ( SELECT TOP (( @derivedKeyLength + @hmacLength - 1 ) / @hmacLength )
 ROW_NUMBER() OVER ( ORDER BY ( SELECT NULL )) [Counter],
 @salt + CAST(ROW_NUMBER() OVER ( ORDER BY ( SELECT NULL )) AS binary(4)) U
 FROM sys.all_objects
 ORDER BY [Counter] ASC ) OuterLooper
 CROSS APPLY dbo.Hmac( @password, OuterLooper.U ) uAOuter

After that I got really stuck on how to calculate @uA in terms of itself; I still think that there is probably some really, really clever APPLY wizardry to get this, but I spent a few hours going nowhere on that one. Instead, I ultimately settled on a recursive CTE to get the base case and then do the calculation.

WITH InnerLoopRecursive AS
(
 SELECT tA.Hash uA,
 tB.Hash uB,
 OuterLoop.Counter OuterCount,
 1 [Counter]
 FROM ( SELECT uAOuter.Hash UA,
 uAOuter.Hash UB,
 OuterLooper.Counter
 FROM ( SELECT TOP (( @derivedKeyLength + @hmacLength - 1 ) / @hmacLength )
 ROW_NUMBER() OVER ( ORDER BY ( SELECT NULL )) [Counter],
 @salt + CAST(ROW_NUMBER() OVER ( ORDER BY ( SELECT NULL )) AS binary(4)) U
 FROM sys.all_objects
 ORDER BY [Counter] ASC ) OuterLooper
 CROSS APPLY dbo.Hmac( @password, OuterLooper.U ) uAOuter ) OuterLoop
 CROSS APPLY dbo.Hmac( @password, OuterLoop.UA ) tA
 CROSS APPLY ( VALUES (
 -- unrolled loop to XOR uA and uB
 CAST(SUBSTRING( tA.Hash, 1, 8 ) ^ CAST(SUBSTRING( OuterLoop.UB, 1, 8 ) AS bigint) AS binary(8)) + CAST(SUBSTRING( tA.Hash, 9, 8 ) ^ CAST(SUBSTRING( OuterLoop.UB, 9, 8 ) AS bigint) AS binary(8)) + CAST(SUBSTRING( tA.Hash, 17, 8 ) ^ CAST(SUBSTRING( OuterLoop.UB, 17, 8 ) AS bigint) AS binary(8)) + CAST(SUBSTRING( tA.Hash, 25, 8 ) ^ CAST(SUBSTRING( OuterLoop.UB, 25, 8 ) AS bigint) AS binary(8)))) tB ( [Hash] )
 UNION ALL
 SELECT tA.Hash uA,
 tB.Hash uB,
 InnerLoopRecursive.OuterCount,
 InnerLoopRecursive.Counter + 1
 FROM InnerLoopRecursive
 CROSS APPLY dbo.Hmac( @password, InnerLoopRecursive.uA ) tA
 CROSS APPLY ( VALUES (
 -- unrolled loop to XOR uA and uB
 CAST(SUBSTRING( tA.Hash, 1, 8 ) ^ CAST(SUBSTRING( InnerLoopRecursive.uB, 1, 8 ) AS bigint) AS binary(8)) + CAST(SUBSTRING( tA.Hash, 9, 8 ) ^ CAST(SUBSTRING( InnerLoopRecursive.uB, 9, 8 ) AS bigint) AS binary(8)) + CAST(SUBSTRING( tA.Hash, 17, 8 ) ^ CAST(SUBSTRING( InnerLoopRecursive.uB, 17, 8 ) AS bigint) AS binary(8)) + CAST(SUBSTRING( tA.Hash, 25, 8 ) ^ CAST(SUBSTRING( InnerLoopRecursive.uB, 25, 8 ) AS bigint) AS binary(8)))) tB ( [Hash] )
 WHERE InnerLoopRecursive.Counter + 1 < @iterations
)

After that I was really hoping to get away with just an aggregate (or maybe a window function), but apparently you can't do that with varbinary(MAX), so I had to do another recursive CTE.

, DerivedKeyPerOuterLoop AS
(
 SELECT CONVERT( varbinary(MAX), '' ) DerivedKey,
 0 [Counter]
 UNION ALL
 SELECT DerivedKeyPerOuterLoop.DerivedKey + CONVERT( varbinary(MAX),
 CASE WHEN DerivedKeyPerOuterLoop.Counter = (( @derivedKeyLength + @hmacLength - 1 ) / @hmacLength ) THEN LEFT(InnerLoopRecursive.uB, @derivedKeyLength - ((( @derivedKeyLength + @hmacLength - 1 ) / @hmacLength ) - 1 ) * @hmacLength)
 ELSE InnerLoopRecursive.uB END ) DerivedKey,
 DerivedKeyPerOuterLoop.Counter + 1
 FROM DerivedKeyPerOuterLoop
 INNER JOIN InnerLoopRecursive
 ON ( DerivedKeyPerOuterLoop.Counter + 1 ) = InnerLoopRecursive.OuterCount
 WHERE InnerLoopRecursive.Counter = @iterations - 1
)

Throughout the recursive CTEs the JOINs get pretty funky as we're trying to handle a potential granularity explosion, but it should work okay-ish.

Once we have that final CTE, then we just need to get the result from the last iteration:

CREATE OR ALTER FUNCTION dbo.Pbkdf2_modified
(
 @password varbinary(8000),
 @salt varbinary(7996),
 @iterations int = 1000,
 @derivedKeyLength int = 32,
 @hmacLength int = 32
)
RETURNS table
AS
 RETURN ( WITH InnerLoopRecursive AS
 (
 SELECT tA.Hash uA,
 tB.Hash uB,
 OuterLoop.Counter OuterCount,
 1 [Counter]
 FROM ( SELECT uAOuter.Hash UA,
 uAOuter.Hash UB,
 OuterLooper.Counter
 FROM ( SELECT TOP (( @derivedKeyLength + @hmacLength - 1 ) / @hmacLength )
 ROW_NUMBER() OVER ( ORDER BY ( SELECT NULL )) [Counter],
 @salt + CAST(ROW_NUMBER() OVER ( ORDER BY ( SELECT NULL )) AS binary(4)) U
 FROM sys.all_objects
 ORDER BY [Counter] ASC ) OuterLooper
 CROSS APPLY dbo.Hmac( @password, OuterLooper.U ) uAOuter ) OuterLoop
 CROSS APPLY dbo.Hmac( @password, OuterLoop.UA ) tA
 CROSS APPLY ( VALUES (
 -- unrolled loop to XOR uA and uB
 CAST(SUBSTRING( tA.Hash, 1, 8 ) ^ CAST(SUBSTRING( OuterLoop.UB, 1, 8 ) AS bigint) AS binary(8)) + CAST(SUBSTRING( tA.Hash, 9, 8 ) ^ CAST(SUBSTRING( OuterLoop.UB, 9, 8 ) AS bigint) AS binary(8)) + CAST(SUBSTRING( tA.Hash, 17, 8 ) ^ CAST(SUBSTRING( OuterLoop.UB, 17, 8 ) AS bigint) AS binary(8)) + CAST(SUBSTRING( tA.Hash, 25, 8 ) ^ CAST(SUBSTRING( OuterLoop.UB, 25, 8 ) AS bigint) AS binary(8)))) tB ( [Hash] )
 UNION ALL
 SELECT tA.Hash uA,
 tB.Hash uB,
 InnerLoopRecursive.OuterCount,
 InnerLoopRecursive.Counter + 1
 FROM InnerLoopRecursive
 CROSS APPLY dbo.Hmac( @password, InnerLoopRecursive.uA ) tA
 CROSS APPLY ( VALUES (
 -- unrolled loop to XOR uA and uB
 CAST(SUBSTRING( tA.Hash, 1, 8 ) ^ CAST(SUBSTRING( InnerLoopRecursive.uB, 1, 8 ) AS bigint) AS binary(8)) + CAST(SUBSTRING( tA.Hash, 9, 8 ) ^ CAST(SUBSTRING( InnerLoopRecursive.uB, 9, 8 ) AS bigint) AS binary(8)) + CAST(SUBSTRING( tA.Hash, 17, 8 ) ^ CAST(SUBSTRING( InnerLoopRecursive.uB, 17, 8 ) AS bigint) AS binary(8)) + CAST(SUBSTRING( tA.Hash, 25, 8 ) ^ CAST(SUBSTRING( InnerLoopRecursive.uB, 25, 8 ) AS bigint) AS binary(8)))) tB ( [Hash] )
 WHERE InnerLoopRecursive.Counter + 1 < @iterations
 ),
 DerivedKeyPerOuterLoop AS
 (
 SELECT CONVERT( varbinary(MAX), '' ) DerivedKey,
 0 [Counter]
 UNION ALL
 SELECT DerivedKeyPerOuterLoop.DerivedKey + CONVERT( varbinary(MAX),
 CASE WHEN DerivedKeyPerOuterLoop.Counter = (( @derivedKeyLength + @hmacLength - 1 ) / @hmacLength ) THEN LEFT(InnerLoopRecursive.uB, @derivedKeyLength - ((( @derivedKeyLength + @hmacLength - 1 ) / @hmacLength ) - 1 ) * @hmacLength)
 ELSE InnerLoopRecursive.uB END ) DerivedKey,
 DerivedKeyPerOuterLoop.Counter + 1
 FROM DerivedKeyPerOuterLoop
 INNER JOIN InnerLoopRecursive
 ON ( DerivedKeyPerOuterLoop.Counter + 1 ) = InnerLoopRecursive.OuterCount
 WHERE InnerLoopRecursive.Counter = @iterations - 1
 )
 SELECT DerivedKeyPerOuterLoop.DerivedKey
 FROM DerivedKeyPerOuterLoop
 WHERE DerivedKeyPerOuterLoop.Counter = (( @derivedKeyLength + @hmacLength - 1 ) / @hmacLength ));

• Kittoes0124: Love the effort and your liberal use of apply (my favorite operator). I too got stuck on how to calculate @uA in terms of itself and the recursive solution is somewhat clever (I love it, but I hate it!).