5
\$\begingroup\$

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...

\$\endgroup\$
  • \$\begingroup\$ Please, avoid posting many questions in a row. Post one, wait until you get an answer, wait a day, and post another one \$\endgroup\$ – Caridorc Oct 17 '15 at 20:52
  • \$\begingroup\$ @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. \$\endgroup\$ – Kittoes0124 Oct 17 '15 at 20:58
  • \$\begingroup\$ Sure you did well, my bad, I did not look carefully enough at the main page... Hope you get some nice answers. \$\endgroup\$ – Caridorc Oct 17 '15 at 21:00
1
\$\begingroup\$

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 ));
\$\endgroup\$
  • \$\begingroup\$ 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!). \$\endgroup\$ – Kittoes0124 Aug 23 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.