[2123] in Kerberos_V5_Development
[sci.crypt] Kerberos IVEC Attack
daemon@ATHENA.MIT.EDU (Barry Jaspan)
Thu Dec 19 11:52:13 1996
Date: Thu, 19 Dec 1996 16:52:04 GMT
From: "Barry Jaspan" <bjaspan@MIT.EDU>
To: krbdev@MIT.EDU
------- Start of forwarded message -------
From: Adrian M Iley <iley+@andrew.cmu.edu>
Subject: Kerberos IVEC Attack
Newsgroups: sci.crypt
Date: Wed, 18 Dec 1996 14:47:42 -0500
Organization: Junior, Computer Science, Carnegie Mellon, Pittsburgh, PA
Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!eru.mt.luth.se!www.nntp.primenet.com!nntp.primenet.com!howland.erols.net!cliffs.rs.itd.umich.edu!portc01.blue.aol.com!newsstand.cit.cornell.edu!news.acsu.buffalo.edu!dsinc!newsfeed.pitt.edu!bb3.andrew.cmu.edu!andrew.cmu.edu!iley+
Lines: 520
Message-ID: <Mmi4dSe00YUo0sjkY0@andrew.cmu.edu>
NNTP-Posting-Host: po8.andrew.cmu.edu
Note: A much more readable version of this draft is available in a html format.
The URL is "http://www.cs.cmu.edu/afs/cs/usr/iley/www/kerbatck/kerbatck.html"
This is currently a draft, so there are updates to come.
======================================================================
Kerberos IVEC Attack [DRAFT]
By: Adrian Iley
(c) 1996, Adrian Iley
If you have any questions/comments/additions/suggestions/errata,
send email to: iley+@andrew.cmu.edu and/or post to: sci.crypt.
----------------------------------------------------------------------
I do not know if anybody has discovered this problem with Kerberos before.
If someone has, please let me know.
If so, I don't mind re-inventing the wheel, at least I learned how to think.
You may copy or modify this document as long as you try to give credit
where it is due.
This paper first explains a vulnerability that may arise within
protocols that use an encryption key K as an IVEC for a block encryption
mode during communications. (i.e. PCBC, CBC, etc.) And how this
vulnerability may let a man in the middle attacker discover the
encryption key K, with very little computation (a few xors). This attack
was originally explained to me by David Wagner in a sci.crypt post which
replied to some paranoid questions I had about IVEC=K.
The attack is summarized well by David Wagner:
"This attack requires one chosen-ciphertext query, a little bit of
known plaintext, and very little computation."
Secondly, I explain an extension to David's attack on PCBC which may
make it more useful against certain protocols.
Thirdly, the paper explains that Kerberos V4 (I'm currently checking on
V5) by the same improper handling of IVECs may be making many
protocols/applications that use the Kerberos session keys for
communications vulnerable to the same attack. If the attack is possible,
the attacker will gain the Kerberos session key, and thus can use
Kerberos tickets to masquerade as the client or server for the lifetime
of the stolen ticket.
Finally, I give some possible attack scenarios, possible fixes for the
problem, and some references.
----------------------------------------------------------------------
Table of Contents
1) Story: The story of how all of this came about.
2) Notation: First a little bit of notation.
3) PCBC Attack: David Wagner's PCBC attack.
4) PCBC Attack Extension: My extension to the PCBC attack.
5) Kerberos Problems: My extension to the PCBC attack.
6) Attack Scenarios: Possible ways of mounting an attack.
7) Fixes/Lessons Learned: Possible ways of fixing this problem and some
lessons I learned.
8) References/Acknowledgments: People and things who helped me learn
about all of this.
===============================PAGE_ONE===============================
Kerberos IVEC Attack: Story
NOTE: This page currently needs heavy construction
I will add a story here, explaining how I learned about all of this, and
how I found the problems.
For now, please go on to the next page there is a bit of real meat there.
NOTE: This page currently needs heavy construction
===============================PAGE_TWO===============================
Kerberos IVEC Attack: Notation
K : The encryption key being used.
P[n] : Where n is some integer greater than or equal to 0, is the n'th
chunk of plaintext. For example: with DES this is the n'th 8 byte chunk
of data which is being encrypted.
C[n] : This is the n'th chunk of ciphertext. For example: with DES this
is the n'th 8 byte chunk of ciphertext.
IVEC : The initial vector for a chaining mode encryption. For example:
CBC, PCBC, CFB, and so on.
VEC[n] : The n'th vector going into the encryption and decryption of the
n+1'th block of ciphertext. Note: be careful when reading about VEC,
this notation of mine is now stating that VEC[0] is the vector used for
C[1]. So from this it follows that VEC[-1] would be IVEC. I will just
use the term IVEC instead for this special case.
Decrypt(C[n]) : The decryption of the ciphertext block C[n] with the
specified key (i.e. K) in the specified encryption mode (i.e. PCBC).
Encrypt(P[n]) : The encryption of the plaintext block P[n] with the
specified key, in the specified encryption mode.
Prime : This is the symbol "'", it will primarily be used to denote some
other encryption using the same encryption key, K. For example P'[n]
Parenthesis : () these are usually used to denote precedence with
regards to some sort of order. I will primarily be using them to show
where something came from, and not specifically to force an order. For
example: for PCBC VEC[n] = (C[n] xor P[n]).
==============================PAGE_THREE==============================
Kerberos IVEC Attack: PCBC Attack
Originally posted to sci.crypt by David Wagner,
rewritten by Adrian Iley.
This is a chosen-ciphertext query attack, which shows how to recover the
encryption key K from an improperly used PCBC encryption, namely one
that uses K as its IVEC.
So, in this case we are assuming IVEC = K, for the PCBC encryption that
contains P[0] and that IVEC' = anything for the encryption starting with
P'[0].
The attack is summarized well by David Wagner:
"This attack requires one chosen-ciphertext query, a little bit of
known plaintext, and very little computation."
----------------------------------------------------------------------
Suppose that we know the first block of plaintext P[0] in a PCBC
encryption that uses the key K. Perhaps its a known header, or something
easy to guess at.
Since this may be some known header, we assume that attacker knows:
P[0] = some known value
Now since the attacker can see the ciphertext the attacker knows:
C[0] = Encrypt(P[0] xor K)
Now, say we have some other (or possibly the same) PCBC encryption that
uses the same key K. We would normally have the following:
C'[0], C'[1], ..., C'[n], C'[n+1], C'[n+2], ...
If the attacker knows some piece of plaintext P'[n] that is being
encrypted, he can launch the following active attack. The attacker
places C[0] into the encryption stream after C'[n]. So the cipher text
stream will now look like the following:
C'[0],C'[1],...,C'[n],C[0],...
Now since the attacker changed the ciphertext the entity which is doing
the decryption will see:
P'[0],P'[1],...,P'[n],P''[n+1],P''[n+2],...
As David Wagner says:
"(Remember that we injected an "error" into the block numbered n+1,
so the decrypted plaintext will match the original sent plaintext for
blocks 0,1,...,n but thereafter will depart.)"
Now the decryption of the injected C[0] will be the following:
P''[n+1] = Decrypt(C[0]) xor VEC'[n]
= Decrypt(C[0]) xor (C'[n] xor P'[n])
= P[0] xor K xor (C'[n] xor P'[n])
Since this is a chosen-ciphertext attack, we can make the assumption
that the attacker will be able to learn what P''[n+1] is. A discussion
of how this may be done is presented later.
So the attacker now knows the following:
P[0], C[0], P'[n], C'[n], P''[n+1]
So the attacker can now recover K as:
K = (P[0] xor K) xor VEC'[n] xor P''[n+1]
= (P[0] xor K) xor (C'[n] xor P'[n]) xor (P[0] xor (C'[n] xor P'[n]))
----------------------------------------------------------------------
Similar attacks are possible against the various popular blocked
encryption modes (CBC, PCBC, CFB, etc.) It is even possible to use the
knowledge of P[0] and the C[0] from a PCBC encryption and apply them to
an active attack in these various other stream modes that use the same K
and still be able to learn what K is.
==============================PAGE_FOUR===============================
Kerberos IVEC Attack: PCBC Attack Extension
This is an addition to the attack mentioned on the previous page, which
may make it easier to attack a protocol which uses PCBC as its
encryption mode.
----------------------------------------------------------------------
You may remember the following from the previous page:
As David Wagner says:
"(Remember that we injected an "error" into the block numbered
n+1, so the decrypted plaintext will match the original sent plaintext
for blocks 0,1,...,n but thereafter will depart.)"
One problem is that PCBC is not very tolerant with errors. An attacker
might foil his attempts at getting P''[n+1] by the fact that the rest of
the plaintext which is decrypted by the receiver will be garbled.
Here is the addition, if the attacker injects two C[0]'s into the
encryption instead of just one, and then makes it so C'[n+1], C'[n+2],
... follow this, the following blocks will decrypt properly. Note
however, that the remaining plaintext will be offset by 16 bytes. This
may or may not be a problem, depending on the protocol which is being
attacked.
This will make it so a PCBC ciphertext stream of the form:
C'[0], C'[1], ..., C'[n], C[0], C[0], C'[n+1], C'[n+2], ...
will decrypt to the following:
P'[0], P'[1], ..., P'[n], P''[n+1], P''[n+2], P'[n+1], P'[n+2], ...
Here is a more rigorous description:
So what we want is the next VEC, which is VEC''[n+2] to be equal to the
VEC'[n] which would have been used for decrypting C'[n+1]. This VEC
should be equal to (P'[n] xor C'[n]).
We already know from before that:
P''[n+1] = Decrypt(C[0]) xor VEC'[n]
= Decrypt(C[0]) xor (C'[n] xor P'[n])
= (P[0] xor K) xor (C'[n] xor P'[n])
This means that the next VEC will be:
VEC''[n+1] = C[0] xor P''[n+1]
Now this new VEC will go into the decryption of the next block of
ciphertext, which is our second C[0].
So, the second C[0] will decrypt to:
P''[n+2] = Decrypt(C[0]) xor VEC''[n+1]
= Decrypt(C[0]) xor (C[0] xor P''[n+1])
= (P[0] xor K) xor (C[0] xor ((P[0] xor K) xor (C'[n] xor P'[n])))
= C[0] xor (C'[n] xor P'[n])
From this it follows that the next VEC, will be:
VEC''[n+2] = C[0] xor P''[n+2] =
C[0] xor (C[0] xor (C'[n] xor P'[n])) =
(C'[n] xor P'[n])
Since this is the proper VEC for the original ciphertext C'[n+1], this
ciphertext and the ones that follow will decrypt to original plaintext.
==============================PAGE_FIVE===============================
Kerberos IVEC Attack: Kerberos Problems
OK, so when I originally started asking around about the security of
using the DES key for an IVEC. David Wagner's PCBC Attack response
sounded great. It showed that an encrypted communications library that
we were using at my work is possibly vulnerable to his attack. In fact,
I came up with a working attack against an application that we are
currently working on which uses this library. At the time of David's
response, he didn't know that I was referring to a package at work and
he asked the following:
"What system is this? Is this Kerberos?"
Now, I responded to this by thanking everyone for their help and saying
not to worry, its just a communications package that we use at work, and
we will just fix it.
Well, one night I was lying in bed awake, and I thought to myself. So
what is it that Kerberos does. So, I started looking at the sources for
Kerberos V4 which were sitting on my hard drive. OOPS, they use the
session key as an IVEC when they use encryption.
Now here is a problem with Kerberos V4 , it uses the Kerberos session
key as an IVEC into the DES PCBC routine. I'm not sure if this is still
done within the current Kerberos V5 release, I'm currently working on
figuring that one out. Remember, this is a bad thing to do, if using any
of the standard chaining modes, it is not a thing particular to PCBC.
The same problem exists in CBC, and is even somewhat easier to break.
More specifically whenever a request to a server is made (krb_mk_req),
or a mutual authentication response is made (krb_mk_priv), the
authenticator that is made is PCBC encrypted using the session key as an
IVEC. There are probably other cases of Kerberos doing similar things,
but these are probably the most used functions that do.
Now, this wouldn't be a problem if the plaintext within the first 8 byte
block of ciphertext of these authenticators was hard to guess. (i.e. its
a large random number) But this isn't the case.
Here are two cases which I will focus on:
The Client's Authenticator:
When a client wants to send a Kerberos request to a service, the client
asks the Kerberos TGS for a ticket for the service. The response is a
session key, some other info and a ticket that only the server can read.
The client makes an authenticator, which is a request that tells who the
client is, and it also contains a checksum value which may be used for
mutual authentication. The client then encrypts this authenticator using
PCBC encrypt with the IVEC=K. The client then sends the ticket which the
server can only read along with the client's authenticator.
This authenticator generated by the client the looks like the following:
Encrypt(Principle Name, Principle Instance, Local Realm, ...)
So essentially, if I "iley" ask for the "rcmd" service on the machine
"unix20.andrew.cmu.edu". I get a ticket from the Kerberos TGS which, I
need to send to the service, this ticket along with an authenticator
which I build and encrypt in PCBC mode with the session key as an IVEC.
This would look like the following:
Encrypt(iley\0\0ANDREW.CMU.EDU\0 ...)
Now, this authenticator contains more than the required 8 bytes of
fairly predictable plaintext. Being able to guess that "iley" is
requesting a certain service, may not be hard at all. For instance, on a
UNIX system the attacker may use the "ps" command to see who is doing
what and when (i.e. who just logged in).
So the first block of ciphertext in the Kerberos authenticator which is
generated by the client, now may make us vulnerable to the before
mentioned attack that could reveal the Kerberos session key, thus
allowing the attacker to masquerade as the client or server for the
lifetime of the ticket.
The Server's Authenticator:
If mutual authentication is used (i.e. with sendauth/recvauth), the
server will have to send a reply back to the client. This reply
authenticator consists of the following (once again encrypted with
IVEC=K):
Encrypt(0x00000004[cksum+1])
Depending on your protocol the 4 byte checksum value may vary from being
fixed to being a random value. So, if an attacker gains the information
he needs from mounting an attack, he will be able to guess the key in
anywhere from time=1 to time=2^32. The attacker can easily check if his
guess at the checksum is right by decrypting the ciphertext using the
guessed key, and looking for the correct values.
Note: All of this encrypted Kerberos ticket information, being sent back
and forth between the client and server can easily be grabbed by a man
in the middle.
Also: Please correct me if the Kerberos terminology that I am using is off.
===============================PAGE_SIX===============================
Kerberos IVEC Attack: Attack Scenarios
NOTE: This page currently needs heavy construction
I have a small list of feasible situations where an attacker may
succeed, and much longer and more detailed explanations of what I have
below:
David Wagner mentioned the following:
"I think this attack may even be practical to mount in real life, if
you can mount an active attack. Known plaintext is often available in
the form of predictable headers, stereotyped text, etc. Chosen
ciphertext queries are often available: for example, in an encrypted
telnet application, you wait till the person is in the middle of typing
an email message; then you inject some chosen ciphertext, let them
finish & send off the message, and watch as the email is transmitted (in
the clear!) to/from the SMTP server, recovering the decryption of the
chosen ciphertext in the process."
I have a few more specific attacks, I have much more detailed
explanations than what is below, they will be inserted when I have more
time to do so:
Attacks on the "rcmd" ticket by looking at Telnet sessions. (i.e.
all the way from waiting for someone to make a temporary clear Telnet
session out of an encrypted session, to peeking on screen of person near
to you)
Also, an attack "which works" on a previous version of application
that we are working on at work.
Please let me know if you have any other scenarios, or if someone
actually mounts a successful attack. I'd love to add them.
NOTE: This page currently needs heavy construction
==============================PAGE_SEVEN==============================
Kerberos IVEC Attack: Fixes/Lessons
----------------------------------------------------------------------
Fixes: What you can do now for your protocol.
Encrypted Key Exchange:
One way to make sure that your protocol isn't vulnerable to this problem
with Kerberos is to generate a different key for each communication.
This also has the nice effect of making it so we don't have some replay
problems. The following algorithm was suggested to me by one of my
co-workers, Jeffrey Hutzelman:
A and B both share a key K0. (i.e. the Kerberos session key)
B chooses key K1 (randomly), encrypts it with K0, and sends it to A.
A chooses key K2 (randomly), encrypts it with K1, and sends it to B.
K2 is used for encrypting the data-stream.
This should be done immediately after Kerberos authentication.
This is the most unobtrusive solution I have found so far.
Cryptographic One-Way Hash:
If you send a cryptographic one-way hash (i.e. MD5) of the plaintext
along with the ciphertext, the receiver will be able to check the
integrity of the message and reject modified messages. This should
thwart a query attack. This may not always be the best solution,
especially if you are streaming.
Note: depending on your program and operating system it may be important
to zero any memory containing any rejected plaintext so an attacker
cannot recover it from a deallocated block of memory, or by other means.
Prove that your protocol isn't vulnerable to this "query" attack.
This may be extremely hard to do. Also, note it is very easy to falsely
trick yourself into believing that your system isn't vulnerable when it
really is. I've seen this a few times. Remember, attackers often come up
with new and extremely clever ways of attacking.
----------------------------------------------------------------------
Fixes: What should be done in general.
Different IVECs:
Whenever A and B want to communicate using a given key K (Currently we
should also avoid using the Kerberos session key to encrypt) in a
feedback mode, they should use different IVECs. This will eliminate
replay problems. Also, it is very important that there isn't any
relation between the IVECs and the session key K, we don't want to leak
any key information.
Every time A & B wants to communicate with the same key.
A selects a new IVECa and sends it to B (in the clear)
B selects a new IVECb and sends it to A (in the clear)
A encrypts and B decrypts A's message using IVECa
B encrypts and A decrypts B's message using IVECb
One way around having to do this many times during a session, is to
"extend" the IVEC. The next communication (send) using the same K, will
just use a new IVEC that would have been the next VEC if there would be
one more block of data to encrypt. (i.e. for PCBC the next IVEC used
would be the last piece of plaintext xor the last piece of ciphertext)
So, the communications going from a person to another just looks like a
huge chunk of encrypted data.
A less secure option would be to use a fixed IVEC (i.e. 0 or some other
choice). This is still more secure than using the IVEC=K option, but it
may be vulnerable to a precomputation attack. Although, not entirely
practical, this attack does weaken the security you get by generating a
different IVEC for each communication. The attack follows:
The attacker knows that the first block of data P[0] is a known
fixed value, or its fairly often the same (i.e. a fixed header, or only
one of a couple of values) For each of the 2^n possible keys K, the
attacker does the following, encrypt P[0] using the fixed IVEC in the
specified encryption mode. Use the ciphertext as an index to store the
key K in a huge table. Now all future and past communications keys can
be broken in O(1) time. This is a significant weakening of the security
that could be had by exchanging different IVECs, even if it is not
entirely feasible to generate such a table using today's technology.
Instead of needing to attempt a 2^n brute force search (or the next best
attack) for each new key which is used, we only have to do a O(1) table
lookup. Also note, there are variations on the table generation/storage
which allow us to store less data at the expense of a slower lookup time.
----------------------------------------------------------------------
Fixes: What could be done to fix Kerberos.
Different IVECs:
Each authenticator which is built should be encrypted with a different
IVEC. The IVEC can be stored in the clear with the encrypted
authenticator. This IVEC could be a random number, or some other option.
Mainly, it is very important that there isn't any relation with the
session key K.
This is easy to do and would entirely fix this particular problem with
Kerberos.
==============================PAGE_EIGHT==============================
Kerberos IVEC Attack: References/Acknowledgments
Adrian Iley: Wrote this document. Was paranoid about IVEC=K and asked.
Came up with the PCBC attack extension. Found that Kerberos makes the
IVEC=K attack still possible and researched it. Dreamed up some of the
fixes against the attack and attack scenarios.
Part Time: Systems Programmer
CMU School of Computer Science, Research Computing Facility
Full Time Student: CMU School of Computer Science (SCS)
David Wagner: Gave me the PCBC IVEC=K attack. For this I am very
grateful. He also gave me an attack scenario.
Researching cryptography and computer security in the ISAAC project
at UC Berkeley
Graduate student at UC Berkeley
Jeffrey Hutzelman: Has been helpful in general with all of this. Gave me
the encrypted key exchange protocol.
Full Time: Systems Programmer
CMU School of Computer Science, Research Computing Facility
John Prevost: Has also been helpful with this.
Full Time: Systems Programmer
CMU School of Computer Science, Research Computing Facility
Student: CMU School of Computer Science (SCS)
Kerberos: Sources for Kerberos V4 and Kerberos V5 can be found at
athena-dist.mit.edu
Mike Accetta: My job supervisor.
Manager of Systems Programming
CMU School of Computer Science, Research Computing Facility
Many Others: Posted to sci.crypt about precomputed lookup table attacks.
----------------------------------------------------------------------
If you have any questions/comments/additions/suggestions/errata,
send email to: iley+@andrew.cmu.edu and/or post to: sci.crypt.
(c) 1996, Adrian Iley
------- End of forwarded message -------
