Re: Can Kerberos be cracked??
From: Laura A. Robinson (larobins@bellatlantic.net)Date: 10/26/01
- Previous message: Jim Harrison (SPG): "RE: Something about ISA Server 2000..."
- In reply to: Doug Foster: "Re: Can Kerberos be cracked??"
- Next in thread: Bruce Marshall: "RE: Can Kerberos be cracked??"
- Next in thread: Perkins, Sharon MSER:EX: "RE: Can Kerberos be cracked??"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Message-ID: <038b01c15ddb$271df420$0b00010a@lauradominion.com> From: "Laura A. Robinson" <larobins@bellatlantic.net> To: "Doug Foster" <fosterd@airshow.net>, "Bruce Marshall" <brucem@lucent.com>, "'Bugger Bugtraq'" <somebug@hotmail.com>, "Focus on Microsoft Mailing List" <FOCUS-MS@SECURITYFOCUS.COM> Subject: Re: Can Kerberos be cracked?? Date: Fri, 26 Oct 2001 01:00:36 -0400
Please look at the details of what the salt value may be; it's not simply a
matter of appending a couple of bytes. Again, you would have to know the
salt value *and* the salt algorithm (if there is one), plus every
dictionary word, *plus* the algorithm used to generate the key. We're not
just talking a very large dictionary and a lot of CPU cycles; we're talking
*exponential*, *even* if you know how the particular salt was derived.
Let's see if I can clear this up a little bit...(I'm not a math geek, be
warned)
Say you decide that you're going to run encryption keys against a packet you
have snagged off of a network, and that packet contains the encrypted field
that contains the timestamp and other preauthentication data. Let's assume
we're dealing with 128-bit encryption here.
There are something like 340,282,366,920,938,463,463,374,607,431,768,211,456
possible keys, of which *one* can decrypt those fields.
So, you decide that you're going to generate all of these possible keys, and
you're going to do this with a dictionary. You would have to take every
dictionary word combined with every possible salt value (which you would
first have to figure out). Let's now make a whole bunch of really
conservative assumptions (one of which is, of course, that we're not dealing
with multi-byte characters in any of this- a pretty safe assumption).
See, here's the nifty thing about these non-reversible hashing algorithms-
they take variable length strings and produce fixed-length results. You
wouldn't even have any idea how *many* characters were even hashed in the
first place, with or without a salt.
Let's say the salt is ten bytes in length (the reality is, it's probably
significantly longer than that; of course, you have no real way of knowing).
Ten bytes = 80 bits.
2^80 = 1,208,925,819,614,629,174,706,176
Therefore, for *each* dictionary word, there are
1,208,925,819,614,629,174,706,176 possible salt values, correct? Again, this
only assumes that the salt value is ten bytes in length.
What if it is twelve bytes? (2^96 = 79,228,162,514,264,337,593,543,950,336)
Anyway, let's go back to ten bytes for a minute. You would have to
concatenate 1,208,925,819,614,629,174,706,176 different values to each
dictionary word (oh, and by the way, you would have to use every possible
case combination of each of those dictionary words- upper, lower, all the
different mixed-cases; don't forget people who stick numbers in their
passwords, too [but we don't even want to go there]), then know what hash
algorithm was used to generate the encryption key, *then* take each of those
concatenated values and generate encryption keys for all of them. Finally,
you would have to use each of those encryption keys to try to decrypt the
encrypted field.
Running your dictionary would be pointless; you'd probably be better off
simply generating random bit values based on length.
Hopefully I didn't dink up any of the math. :-)
Laura A. Robinson
----- Original Message -----
From: "Doug Foster" <fosterd@airshow.net>
To: "Laura A. Robinson" <larobins@bellatlantic.net>; "Bruce Marshall"
<brucem@lucent.com>; "'Bugger Bugtraq'" <somebug@hotmail.com>; "Focus on
Microsoft Mailing List" <FOCUS-MS@SECURITYFOCUS.COM>
Sent: Thursday, October 25, 2001 11:32 PM
Subject: Re: Can Kerberos be cracked??
> Doesn't the random salt value essentially mean that the dictionary must be
> larger, to accomodate the variations of salt? I realize that means a
*very*
> large dictionary, but even so, cracking is just a matter of CPU cycles.
>
> -- Doug
>
> ----- 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: Thursday, October 25, 2001 5:17 PM
> 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
> > >
> > >
> >
> >
> >
>
- Previous message: Jim Harrison (SPG): "RE: Something about ISA Server 2000..."
- In reply to: Doug Foster: "Re: Can Kerberos be cracked??"
- Next in thread: Bruce Marshall: "RE: Can Kerberos be cracked??"
- Next in thread: Perkins, Sharon MSER:EX: "RE: Can Kerberos be cracked??"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
