RE: Can Kerberos be cracked??

From: Bruce Marshall (brucem@lucent.com)
Date: 10/26/01 

From: Bruce Marshall <brucem@lucent.com>
To: "'Laura A. Robinson'" <larobins@bellatlantic.net>, "'Focus on Microsoft Mailing List'" <FOCUS-MS@SECURITYFOCUS.COM>
Subject: RE: Can Kerberos be cracked??
Date: Thu, 25 Oct 2001 17:39:20 -0500
Message-ID: <003d01c15da5$e3d293e0$417c7787@ins.com>

Laura,

Interesting point about the salt. I wasn't aware that Microsoft included
that procedure in their implementation. I actually wasn't aware that any
Kerberos implementation used a salt in combination with the user password
for long-term key creation.

However, upon a quick review of RFC 1510 (IETF standard for Kerberos V5) I
did find a recommendation for password salting that confirms what you've
been writing. In section 6 it states:

"Finally, where a key is to be derived from a user's password, an algorithm
for converting the password to a key of the appropriate type is included.
It is desirable for the string to key function to be one-way, and for the
mapping to be different in different realms. This is important because users
who are registered in more than one realm will often use the same password
in each, and it is desirable that an attacker compromising the Kerberos
server in one realm not obtain or derive the user's key in another."

In the white paper that has been referenced by a few other posters on this
list Microsoft writes this:

"When Alice logs on, for example, the Kerberos client on her workstation
accepts her password and then converts it to a cryptographic key by passing
the text of the password through a one-way hashing function. (All
implementations of Kerberos version 5 must support DES-CBC-MD5. Other
algorithms are permissible.)"

While I'm not going to claim that excludes the possibility of salting, it
doesn't specifically mention Microsoft's Kerberos implementing that step.
Do you have another source that you could point me towards so that I can
review Microsoft's specific salting process?

Regardless, brute force and dictionary attacks are not prevented by salting.
Generally speaking a salt is used to hinder the ability of attackers from
quickly uncovering duplicate passwords in use by multiple users on a system.
Or, as the RFC 1510 doc points out, salting is used to prevent a long term
key in one domain/realm from working in other related domains/realms.

The fact that the salt (and the algorithm) is public knowledge means that
this step only adds time, not security, to the process of cracking a single
password. The attacker can adapt their cracking software to combine
dictionary words or random strings with the salt, hash the two, and then
compare the results with the known hash. If they get a match then they know
they have a working password. 

----
Bruce K. Marshall - brucem@lucent.com - 913-338-5090 x114
Lucent Technologies Worldwide Services - Overland Park, KS

> -----Original Message-----
> From: Laura A. Robinson [mailto:larobins@bellatlantic.net]
> Sent: Thursday, October 25, 2001 4:17 PM
> To: Bruce Marshall; 'Bugger Bugtraq'; Focus on Microsoft Mailing List
> Subject: Re: Can Kerberos be cracked??
>
>
> To clarify further: A "salt" is a "random" value that is
> appended to the
> password before the password is hashed to produce the user's
> long-term key.
> Depending on the implementation of kerberos (non-MIT or MIT),
> the salt that
> is added to the password before it is hashed is either the
> user's complete
> qualified name including kerberos realm (non-MIT
> implementations), or else
> it is an algorithmic value that is stored with the user name
> on the KDC and
> is transmitted securely to the client so that the client can
> perform the
> salting before hashing the password and deriving the
> resultant key (MIT).
>
> Here's what this means:
>
> Suppose my password is "jimbobbillyjoe".
> When my machine hashes my password to produce my key, it
> first obtains a
> salt. Therefore, the actual "word" that is hashed is
> "jimbobbillyjoe" +
> "somevalue".
> Therefore, even if you knew the algorithm that is used to
> produce the key
> and you ran it against the word "jimbobbillyjoe", you would
> not actually be
> hashing what my machine hashed to produce my key. Therefore, it is not
> possible for you to dictionary-crack my password unless you know the
> password, the salt, and the algorithm. If you already knew my
> password,
> there really wouldn't be much point in cracking it, of
> course. Additionally,
> the hashing algorithm that is used to produce my key *is*
> non-reversible, so
> there would be no way for you to determine my password + my
> salt by reverse
> engineering my key.
>
> Hope this helps,
>
> Laura
>
> ----- Original Message -----
> From: "Laura A. Robinson" <larobins@bellatlantic.net>
> To: "Bruce Marshall" <brucem@lucent.com>; "'Bugger Bugtraq'"
> <somebug@hotmail.com>; "Focus on Microsoft Mailing List"
> <FOCUS-MS@SECURITYFOCUS.COM>
> Sent: Wednesday, October 24, 2001 9:13 PM
> Subject: Re: Can Kerberos be cracked??
>
>
> > Well, actually, a salt is added to the password before it is
> (irreversibly)
> > hashed, so a brute force or dictionary attack would not be possible.
> >
> > Laura
> > ----- Original Message -----
> > From: "Bruce Marshall" <brucem@lucent.com>
> > To: "'Bugger Bugtraq'" <somebug@hotmail.com>;
> <focus-ms@securityfocus.com>
> > Sent: Wednesday, October 24, 2001 1:27 PM
> > Subject: RE: Can Kerberos be cracked??
> >
> >
> > > Bugger,
> > >
> > > In order to get the hash you would need to launch a brute
> force attack
> > > against the encrypted timestamp.  If you were able to decrypt the
> > timestamp
> > > that key should be the user's hashed password.
> > >
> > > As for your assumption about the hash being as good as
> the password,
> this
> > is
> > > true to some extend.  Obviously you can't enter that hash into the
> Windows
> > > logon screen, but you could hack together your own client
> that could use
> > the
> > > hash to authenticate.
> > >
> > > If you wanted the password itself you would need to conduct a
> brute-force
> > or
> > > dictionary cracking session to find a match for the hash.
> > >
> > >
> > > ----
> > > Bruce K. Marshall - brucem@lucent.com - 913-338-5090 x114
> > > Lucent Technologies Worldwide Services - Overland Park, KS
> > >
> > >
> > > > -----Original Message-----
> > > > From: Bugger Bugtraq [mailto:somebug@hotmail.com]
> > > > Sent: Tuesday, October 23, 2001 8:48 PM
> > > > To: larobins@bellatlantic.net; fp56@dial.pipex.com;
> > > > focus-ms@securityfocus.com
> > > > Subject: Re: Can Kerberos be cracked??
> > > >
> > > >
> > > > Assuming the steps on user verification u've stated is
> > > > correct (I'm not
> > > > exactly into the details either)....firstly, wouldn't the
> > > > hash (used to
> > > > encrypt the timestamp) still be susceptible to brute-force
> > > > using dictionary
> > > > attacks (or even trying all possible combinations) especially
> > > > since the
> > > > hashing algorithm is known. (maybe even consider maintaining
> > > > a database of
> > > > pre-worked password-hash combinations)
> > > >
> > > > Secondly, even without the actual password known, wouldn't
> > > > juz the hash (let
> > > > say we have managed to get it as what u've stated below) be
> > > > sufficient to
> > > > spoof the authentication (since that hash information is all
> > > > that is needed
> > > > to encrypt the timestamp anyway)???
> > > >
> > > > Did I get what u are saying rite?????
> > > >
> > > >
> > > > >From: "Laura A. Robinson" <larobins@bellatlantic.net>
> > > > >Reply-To: "Laura A. Robinson" <larobins@bellatlantic.net>
> > > > >To: "Phil Pinder" <fp56@dial.pipex.com>,
> <focus-ms@securityfocus.com>
> > > > >Subject: Re: Can Kerberos be cracked??
> > > > >Date: Mon, 22 Oct 2001 20:35:59 -0400
> > > > >
> > > > >Okay, first, looking at my response, it wasn't as clear as I
> > > > would have
> > > > >liked, so let me clarify it.
> > > > >
> > > > >When Jim Bob Billy Joe logs in and types in his password,
> > > > that password is
> > > > >run through a hash (hashing algorithm) to produce a string
> > > > of bytes. The
> > > > >hash itself is non-reversible, which means that it cannot be
> > > > used to derive
> > > > >the password. [*see note at bottom] The resultant set of
> > > > bytes from the
> > > > >hashing of the password is, in this case, the key that is
> > > > then used to
> > > > >encrypt the timestamp. When the KDC receives the
> > > > preauthentication request,
> > > > >it retrieves the user's key (which is the result of the
> > > > hash) and uses that
> > > > >to decrypt the timestamp.
> > > > >
> > > > >Where I feel I wasn't clear in my response was when I
> said that the
> > > > >"resultant hash" generates the encryption key, when what I
> > > > should have said
> > > > >was that the "hashing algorithm" generates the encryption
> > > > key and that the
> > > > >encryption key is then used to encrypt the timestamp.
> > > > Apologies for my
> > > > >distinct lack of clarity; it was a rushed response. :-)
> > > > >
> > > > >Now, on to your question below- when a user's password
> is created or
> > > > >changed, the new password is hashed and the resultant value
> > > > transmitted as
> > > > >the user's new "long-term" (stored in AD and
> encrypted) key. On the
> > > > >occasions when that key needs to be transmitted across the
> > > > wire, it is
> > > > >transmitted using SSL over LDAP, thus protecting the key
> > > > while it is in
> > > > >transit.
> > > > >
> > > > >Now, as for how the authenticating server verifies the
> password- it
> > > > >doesn't.
> > > > >It verifies the key. The server doesn't actually know
> what the user's
> > > > >password is, and doesn't care. What the server does know is
> > > > what the hash
> > > > >result (key) is. When the server receives the
> > > > preauthentication request, it
> > > > >retrieves the user's key from AD and decrypts the timestamp
> > > > with that. If
> > > > >it
> > > > >can successfully decrypt the timestamp with the user's
> key and the
> > > > >timestamp
> > > > >has not expired, then the server knows that the correct key
> > > > (hash result)
> > > > >was used to encrypt the timestamp.
> > > > >
> > > > >So, even if you *could* snag the correct packet off the wire
> > > > and decrypt
> > > > >the
> > > > >timestamp (we're talking significant time here), all that
> > > > would actually
> > > > >tell you is what the byte string was that was used to
> encrypt the
> > > > >timestamp-
> > > > >it wouldn't tell you the user's password.
> > > > >
> > > > >*note at bottom:
> > > > >
> > > > >by referring to the hash algorithm as non-reversible, think
> > > > of it like this
> > > > >(none of this math is valid in any way or meant to represent
> > > > the actual
> > > > >hashing algorithm; I'm just trying to conceptualize how a
> > > > one-way hash
> > > > >works
> > > > >for those who might be unclear)
> > > > >
> > > > >I am your computer. (Obviously, I'm not, but bear with
> me. ;-) )
> > > > >
> > > > >You change your password to "jimbobbillyjoe".
> > > > >
> > > > >I take the word "jimbobbillyjoe" and say to myself, "Okay,
> > > > I'm going to
> > > > >derive the key by counting the number of letters in the
> > > > password (14), then
> > > > >adding five to that number (19). If the result is more than
> > > > one digit in
> > > > >length, I'm going to multiply by five to get another number.
> > > > If it is less
> > > > >than two digits, I am going to multiply it by forty-two.
> > > > (Since result is
> > > > >19, it is multiplied by 5, resulting in 95.) Then I'm going
> > > > to go through
> > > > >the alphabet as many times as it takes to gather the number
> > > > of digits in
> > > > >the
> > > > >result number. (Therefore, I would go through the alphabet
> > > > to produce the
> > > > >following:
> > > > >abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghi
> > > > jklmnopqrstuvwx
> > > > >yzabcdefghijklmnopqrstuvw ) Then I'm going to take all of
> > > > those letters and
> > > > >dump the vowels.
> > > > >(bcdfghjklmnpqrstvwxyzbcdfghjklmnpqrstvwxyzbcdfghjklmnpqrstvw
> > > > xyzbcdfghjklmnp
> > > > >qrstvw). Then I'll assign numeric values to each letter in
> > > > the alphabet,
> > > > >write out all the resulting digits, and that is what I will
> > > > then use as
> > > > >your
> > > > >new long-term key."
> > > > >
> > > > >The point here is, you have no way of knowing exactly how
> > > > the resultant
> > > > >value actually came to be, only what the resultant value
> > > > (key) is, and you
> > > > >can't "undo" what I did to produce it. That key is
> what is used to
> > > > >(reversibly) encrypt the timestamp in your preauthentication
> > > > data, and the
> > > > >key is the only thing that the KDC has associated with you-
> > > > *not* your
> > > > >password itself.
> > > > >
> > > > >I hope this makes sense; I'm high on Nyquil due to having a
> > > > case of the
> > > > >flu.
> > > > >
> > > > >Oh, and if you just want the quick and dirty answer to your
> > > > question (now
> > > > >that I've looked at it again and realized you asked a
> very simple
> > > > >question):
> > > > >
> > > > >The encryption key itself is sent to the authenticating
> > > > server when it is
> > > > >created (*not* when it is used to encrypt a timestamp), and
> > > > it is protected
> > > > >by transmitting it via SSL over LDAP.
> > > > >
> > > > >Hope this helps,
> > > > >
> > > > >Laura Robinson
> > > > >
> > > > >----- Original Message -----
> > > > >From: "Phil Pinder" <fp56@dial.pipex.com>
> > > > >To: "Laura A. Robinson" <larobins@bellatlantic.net>;
> > > > ><focus-ms@securityfocus.com>
> > > > >Sent: Friday, October 19, 2001 6:17 PM
> > > > >Subject: RE: Can Kerberos be cracked??
> > > > >
> > > > >
> > > > > > Thanks for the info Laura
> > > > > >
> > > > > > That raises the question: how does the Authentication
> > > > server verify the
> > > > > > password - by generating the same encryption key? (in
> > > > which case couldnt
> > > > >it
> > > > > > still be reverse engineered?) or is the encryption
> key itself sent
> > > > >encrypted
> > > > > > to the Authentication Server (encrypted with what key?)?
> > > > (I cant find an
> > > > > > explanation at this level of detail without it resorting to
> > > > >cryptographic
> > > > > > algebra)
> > > > > >
> > > > > > Many thanks
> > > > > >
> > > > > > Phil
> > > > >
> > > > >
> > > >
> > > >
> > > >
> _________________________________________________________________
> > > > Get your FREE download of MSN Explorer at
> > > > http://explorer.msn.com/intl.asp
> >
> >

Relevant Pages

  • Re: Can Kerberos be cracked??
    ... Subject: Can Kerberos be cracked?? ... A "salt" is a "random" value that is appended to the ... possible for you to dictionary-crack my password unless you know the ... >> In order to get the hash you would need to launch a brute force attack ...
    (Focus-Microsoft)
  • Re: Can Kerberos be cracked??
    ... Subject: Can Kerberos be cracked?? ... Doesn't the random salt value essentially mean that the dictionary must be ... > possible for you to dictionary-crack my password unless you know the ... >>> In order to get the hash you would need to launch a brute force attack ...
    (Focus-Microsoft)
  • Re: Hash MD5, Sha1 and Length
    ... Salt must always be present, either generated or retrieved form the ... public static String Hash ... // Hash value ... algorithm = new MD5CryptoServiceProvider; ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Hash MD5, Sha1 and Length
    ... These are standard cryptographic methods for protecting bulk passwords ... algorithm = new MD5CryptoServiceProvider; ... The salt prevents two people using the same password having the same ... hash and also stops an attacker pre-calculating hashes for commonly ...
    (microsoft.public.dotnet.languages.csharp)
  • Re:encryption algs
    ... systems is a salted hash algorithm. ... A hash is a numerical value of fixed length which unequivocally ... The intention behind a Salted Hash is to have this type of attack fail ... and only then compute the hash over password and salt. ...
    (Security-Basics)