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

Tobias Markmann <tmarkmann@googlemail.com> Sat, 07 November 2009 12:35 UTC

Return-Path: <tmarkmann@googlemail.com>
X-Original-To: sasl@core3.amsl.com
Delivered-To: sasl@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 21B543A67AE for <sasl@core3.amsl.com>; Sat, 7 Nov 2009 04:35:18 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.214
X-Spam-Level: *
X-Spam-Status: No, score=1.214 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, J_CHICKENPOX_24=0.6, J_CHICKENPOX_43=0.6, J_CHICKENPOX_93=0.6, PLING_QUERY=1.39]
Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id UYpet+SUrWqm for <sasl@core3.amsl.com>; Sat, 7 Nov 2009 04:35:17 -0800 (PST)
Received: from mail-ew0-f218.google.com (mail-ew0-f218.google.com [209.85.219.218]) by core3.amsl.com (Postfix) with ESMTP id C0D1C3A67A6 for <sasl@ietf.org>; Sat, 7 Nov 2009 04:35:16 -0800 (PST)
Received: by ewy18 with SMTP id 18so1573202ewy.43 for <sasl@ietf.org>; Sat, 07 Nov 2009 04:35:35 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=gamma; h=domainkey-signature:mime-version:received:from:date:message-id :subject:to:content-type; bh=MsMx4uJqJ1OSxppRp6a/GVqerU+u92l36v2tSBPtBg0=; b=pWZhqHQpM9GxlEXKC1uEKg/01Bp25jrcbj2XhN5fFA9CQELImQPR2HO1Ugnt4zmNfG pNXTZsmjWuN3/kG/H2FH/YtqXuQ3zGy9IVm3QhcI4Hxu1zDZBsTAsVKIQNvXyCXhFW7o rccsMKxpkD6qK4TqHrltQcxTg+UMVP7boKJLU=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=googlemail.com; s=gamma; h=mime-version:from:date:message-id:subject:to:content-type; b=JJTOSLNy2zbMyF6EzvRS9XPXqSNjmJKKtoXJ7JEZpGKSRZ/QRKygKVM51na0RueB/Z bP4glQazRhGePn4RCUfrZDCntkMfGCLxXb1DWhBSunr8oazm4K8JIR9Oax6akstKwElu q+Gy0sJ+sV0blUR2juUvqD9U2oQq6LptzmGcQ=
MIME-Version: 1.0
Received: by 10.213.3.140 with SMTP id 12mr687369ebn.20.1257597335090; Sat, 07 Nov 2009 04:35:35 -0800 (PST)
From: Tobias Markmann <tmarkmann@googlemail.com>
Date: Sat, 07 Nov 2009 13:35:15 +0100
Message-ID: <5cfc0a8e0911070435s5f894c48rd916f887fb5842d5@mail.gmail.com>
To: sasl@ietf.org
Content-Type: multipart/alternative; boundary="001517491f566db6ad0477c732f8"
Subject: [sasl] SCRAM: PBKDF2 algorithm description wrong?!?
X-BeenThere: sasl@ietf.org
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: SASL Working Group <sasl.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/listinfo/sasl>, <mailto:sasl-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/sasl>
List-Post: <mailto:sasl@ietf.org>
List-Help: <mailto:sasl-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/sasl>, <mailto:sasl-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sat, 07 Nov 2009 12:35:18 -0000

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