Re: [Cfrg] ´ð¸´: Re: ´ð¸´: Re: [saag] New draft: Ha shed Password Exchange

Steven Bellovin <> Thu, 02 February 2012 23:38 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id BEC8121F85F0; Thu, 2 Feb 2012 15:38:15 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -4.882
X-Spam-Status: No, score=-4.882 tagged_above=-999 required=5 tests=[AWL=-0.383, BAYES_00=-2.599, J_CHICKENPOX_23=0.6, J_CHICKENPOX_44=0.6, J_CHICKENPOX_48=0.6, MIME_8BIT_HEADER=0.3, RCVD_IN_DNSWL_MED=-4]
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id nA8Mfjs8a99q; Thu, 2 Feb 2012 15:38:14 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 76A7521F8548; Thu, 2 Feb 2012 15:38:14 -0800 (PST)
Received: from [] ( []) (user=smb2132 mech=PLAIN bits=0) by (8.14.4/8.14.3) with ESMTP id q12NcBwp002473 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT); Thu, 2 Feb 2012 18:38:12 -0500 (EST)
Mime-Version: 1.0 (Apple Message framework v1257)
Content-Type: text/plain; charset=iso-8859-1
From: Steven Bellovin <>
X-Priority: 3 (Normal)
In-Reply-To: <>
Date: Thu, 2 Feb 2012 18:38:11 -0500
Content-Transfer-Encoding: quoted-printable
Message-Id: <>
References: <> <>
To: Dan Harkins <>
X-Mailer: Apple Mail (2.1257)
X-No-Spam-Score: Local
X-Scanned-By: MIMEDefang 2.68 on
Cc:, "" <>
Subject: Re: [Cfrg] =?iso-8859-1?q?=B4=F0=B8=B4=3A_Re=3A__=B4=F0=B8=B4=3A_Re?= =?iso-8859-1?q?=3A__=5Bsaag=5D_New_draft=3A_Ha__shed_Password_Exchange?=
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 02 Feb 2012 23:38:15 -0000

I'll be revising my draft soon.  For now, let me explain a few points.

First -- the primary goal of the draft is avoiding storage of cleartext
passwords, because even strong passwords are easily compromised if the
device or server is hacked.  A second goal is to conceal that the same
password is used for two different users or the same user on two different

It's obviously true that attackers can still launch password-guessing attacks.
This does increase their work factor.  While the difference in work factor
may not be important for targeted attacks, it does help against broad-scale
attacks: can any single password be retrieved?  The way I look at it is
this: for a given effort, how many passwords can the attacker get?  If the
iteration count is doubled, the yield per given effort is obviously halved.

There are no large-scale precomputation attacks possible, because every
hashed password is unique for a given <password,user,service> triple.

I do not see how a random salt would help at all -- it still requires
about the same amount of computation per user per service per guess.
The essential difference between a random salt and my scheme is that
if I change my password to itself, with a random salt the hashed password
would be different; with my scheme, it would be the same.  The attacker's
effort would remain the same.  In addition, a random salt would hurt
usability and/or security.  For the former, consider that I (and many
other people) have many devices with stored passwords.  I personally
use three or four computers and two iToys to read mail.  So -- I set a new
password from one.  I now have to copy down that string and enter it
on five other devices.  Not very user-friendly.  Assume, then, that
the salt is sent as part of the protocol.  That not only hurts adoptability,
since the protocol would now have to have a way to transmit it at the right
point, after it knows the userid but before the authenticator is entered
(quick -- what will that do to, say, IKEv2?), it means that the user's
node would have to have the cleartext password available in order to
hash it with the salt.  But that defeats the purpose of my scheme.
HPW requires no changes to the protocol, and the only possible change
to the implementation is a longer input buffer.

Finally, I'm quite convinced that focusing on strong passwords is fighting
the last war (and, I might add, a war we've lost).  *NO ONE* is using
strong, unique, memorized passwords ubiquitously -- people have too many 
of them to remember.  By actual count, I have >100 web site passwords,
plus login passwords, root passwords, mail passwords, ATM PINs, phone
unlock codes, and more.  Sorry -- EBRAINFULL.  I think that far bigger
dangers are password reuse and node compromise.  HPW is designed to deal
with those threats.

"In a world of smart cards, hand-held authenticators, and zero-
knowledge proofs, it seems pointless to be worrying about poorly-
chosen passwords.  Were the world like that, we might agree.  Today,
it is not."  Mike Merritt and I wrote that about 20 years ago, in
the original EKE paper.  Fortunately, passwords are no longer in use, 
since they've been replaced by better technology, right?  Oh, wait.

On Feb 2, 2012, at 1:46 PM, Dan Harkins wrote:

>  The issue is that hashing a password doesn't make it "random"
> (while it might make it "long"). So no, an ordinary hash is not
> enough. As I suggested, I think a non-secret salt exchanged in
> the protocol can be used as a key to a HMAC and the password can
> be included in the data to be HMAC'd.
>  Dan.
> On Wed, February 1, 2012 5:22 pm, wrote:
>> Well£¬ it is the requirement of the HMAC for key being long and random.
>> Then in the case of the draft, ordinary hash is enough I guess?
>> Regards~~~
>> дÓÚ 2012-02-01 23:49:13:
>>> My take on this is: if you believe that a hash-function is a good
>>> randomizer and can be used in cryptographic key generation process ¨C
>>> then  it does not matter whether what you feed as a "key" input to
>>> HMAC is uniformly distributed or not (because of HMAC internal "hash
>>> spins"). And if you are uneasy on how really random your hash output
>>> is ¨C then a lot of the currently used mechanisms and primitives need
>>> revisiting.
>>> --
>>> Regards,
>>> Uri Blumenthal                            Voice: (781) 981-1638
>>> Cyber Systems and Technology  Fax:    (781) 981-0186
>>> MIT Lincoln Laboratory
>>> From: "" <>
>>> Date: Wed, 1 Feb 2012 03:13:07 -0500
>>> To: Dan Harkins <>
>>> Cc: "" <>rg>, Steven Bellovin
>> <>
>>> Subject: [Cfrg] ´ð¸´: Re: [saag] New draft: Hashed Password Exchange
>>> Hi,all
>>> дÓÚ 2012-01-07 17:03:25:
>>>> On Wed, January 4, 2012 2:56 pm, Steven Bellovin wrote:
>>>>> Good point; let me think about it for -01.  An obvious solution is
>> to send
>>>>> the hostname with the effective password.
>>>>  How is that different than using random salt then? If _something_
>>> is
>>>> going to be sent shouldn't it be a uniformly random bitstring instead
>> of
>>>> a hostname?
>>>>  A uniformly random bitstring would be more appropriate as a key to
>>>> HMAC than a highly structured string like a password too. Iterate
>>>> HMAC(salt, password | service-URI) instead of HMAC(password,
>> service-URI).
>>> I think Dan's suggestion is reasonable, I checked the RFC 2104 and
>>> found the following section :
>>> "3. Keys
>>>   The key for HMAC can be of any length (keys longer than B bytes are
>>>   first hashed using H).  However, less than L bytes is strongly
>>>   discouraged as it would decrease the security strength of the
>>>   function.  Keys longer than L bytes are acceptable but the extra
>>>   length would not significantly increase the function strength. (A
>>>   longer key may be advisable if the randomness of the key is
>>>   considered weak.)
>>>   Keys need to be chosen at random (or using a cryptographically
>>> strong
>>>   pseudo-random generator seeded with a random seed), and periodically
>>>   refreshed.  (Current attacks do not indicate a specific recommended
>>>   frequency for key changes as these attacks are practically
>>>   infeasible.  However, periodic key refreshment is a fundamental
>>>   security practice that helps against potential weaknesses of the
>>>   function and keys, and limits the damage of an exposed key.)"
>>> Since passwords are often not too long, and not so random, it is better
>>> to hash it before using it as a key in a HMAC.
>>> Regards~~~
>>> -Sujing Zhou
>>>>  That said, goal 4 in the draft-- "By iterating a sufficient number
>> of
>>>> times, dictionary attacks can be made arbitrarily expensive"-- seems
>>> a
>>>> bit misguided. The Amazon cloud service has been used to launch an
>>>> off-line dictionary attack against the WPA-PSK protocol which uses
>>>> (HMAC-SHA1) with 4096 iterations to obfuscate a password. This attack
>>>> checks 24,000,000 candidate passwords per minute at a cost of $0.28.
>>>> That's more than 1,600,000,000 iterations per second for about 1/2 a
>> cent.
>>>> So I don't think increased iteration makes dictionary attacks much
>> more
>>>> expensive.
>>>>  Which begs the question, how is this proposal different than
>>> PBKDF2?
>>>> That the "salt" is a service URI?
>>>>  regards,
>>>>  Dan.
>>>>> On Jan 4, 2012, at 5:21 01PM, Joe Touch wrote:
>>>>>> Hi, Steve,
>>>>>> This doc doesn't appear to address the case where a host has
>> multiple
>>>>>> DNS names, which could make it difficult to incorporate the
>> hostname
>>>>>> into the transform. I.e., I could contact a mail server at an IP
>> address
>>>>>> that represents any of dozens of DNS names - how does the server
>> know
>>>>>> which one I used so it can match without exhaustively trying all
>> its
>>>>>> equivalent names?
>>>>>> Joe
>>>>>> On 1/4/2012 1:41 PM, Steven Bellovin wrote:
>>>>>>> I'd appreciate comments on my new draft,
>> draft-bellovin-hpw-00.txt:
>>>>>>> Abstract
>>>>>>>   Many systems (e.g., cryptographic protocols relying on
>> symmetric
>>>>>>>   cryptography) require that plaintext passwords be stored. Given
>> how
>>>>>>>   often people reuse passwords on different systems, this poses a
>> very
>>>>>>>   serious risk if a single machine is compromised.  We propose a
>>>>>>> scheme
>>>>>>>   to derive passwords limited to a single machine from a typed
>>>>>>>   password, and explain how a protocol definition can specify
>> this
>>>>>>>   scheme.
>>>>>>>      --Steve Bellovin,
>>>>>>> _______________________________________________
>>>>>>> saag mailing list
>>>>>      --Steve Bellovin,
>>>>> _______________________________________________
>>>>> saag mailing list
>>>> _______________________________________________
>>>> Cfrg mailing list
>>>> [¸½¼þ "smime.p7s" ±» ÖÜËÕ¾²00132831/user/zte_ltd ɾ³ý]
>>> _______________________________________________
>>> Cfrg mailing list
>> _______________________________________________
>> Cfrg mailing list
> _______________________________________________
> Cfrg mailing list

		--Steve Bellovin,