Subject: [sasl] SCRAM: PBKDF2 algorithm description wrong?!?

From: Tobias Markmann <[email-masked]>
Date: Sat, 7 Nov 2009 13:35:15 +0100

Hi,

http://tools.ietf.org/html/draft-ietf-sasl-scram-10 describes the Hi
function this way:

Hi(str, salt, i):

U0 := HMAC(str, salt + INT(1))
U1 := HMAC(str, U0)
U2 := HMAC(str, U1)
...
Ui-1 := HMAC(str, Ui-2)
Ui := HMAC(str, Ui-1)

Hi := U0 XOR U1 XOR U2 XOR ... XOR Ui

If I interpret this correctly for i = 1 you have to calculate U0 and U1 and
XOR those values.
However this isn't compatible to existing implementations. For i = 1 you
seem to have to return only U0.

This is how I implemented it in Lua:

local function Hi(hmac, str, salt, i)
local Ust = hmac(str, salt.."\0\0\0\1");
 local res = Ust;
for n=1,i-1 do
 Und = hmac(str, Ust)
res = binaryXOR(res, Und)
Ust = Und
 end
return res
end

See the i-1 as upper end of the loop!

So my question: Did I interpret the pseudo code wrong or is the pseudo code
wrong? Would it be problematic to include a couple of test vectors, like
those Simon published (
http://josefsson.org/sasl-gs2/draft-josefsson-pbkdf2-test-vectors.txt) in
the RFC?

Cheers,
Tobias Markmann

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 09 Nov 2009 16:29:55 +0100

> seem to have to return only U0.

Thanks for posting this Tobias.

I believe scram -10 is broken here, the Hi function should not differ
from PBKDF2 in any important way.  Implementers may have access to
PBKDF2 from crypto libraries, and we should encourage them to use it
that way instead of re-implementing a slightly different PBKDF2
algorithm.  The current definition of Hi cannot be implemented using
PBKDF2 due to the +-1 mistake.  Fixing this should be simple, see below
for a editing suggestion from Dave Cridland & me -- although I haven't
verified that it is complete because I would prefer to use a normative
reference to RFC 2898 instead.

> wrong?

I believe the pseudo code in the -10 document is sub-optimal.

> Would it be problematic to include a couple of test vectors, like
> those Simon published (
> http://josefsson.org/sasl-gs2/draft-josefsson-pbkdf2-test-vectors.txt)
> in the RFC?

I have submitted that draft to the IETF now.  It would indeed be useful
to include SCRAM test vectors in the core SCRAM document though.

/Simon

Simon Josefsson <[email-masked]> writes:

> Dave Cridland <[email-masked]> writes:
>
>> On Fri Nov  6 14:10:56 2009, Simon Josefsson wrote:
>>> Here is what I'd prefer.
>>>
>>> OLD:
>>>    o  Hi(str, salt, i):
>>>
>> Change this line to start with U1 instead of U0
>>
>>
>>>       U1   := HMAC(str, U0)
>>
>> Remove this one.
>>
>>
>>>       U2   := HMAC(str, U1)
>>>       ...
>>>       Ui-1 := HMAC(str, Ui-2)
>>>       Ui   := HMAC(str, Ui-1)
>>>
> This has to be 'U1 XOR U2 ... Ui' too.