RE: [WEB SECURITY] Hashing and entropy

["Lavery, Oliver" <oliver@xxxxxxxxxxxxxxxxxxx>]

------_=_NextPart_001_01C8D588.04BBAFAE
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

Hi Nathaniel,

Sorry about the quoting, my webmail client doesn't quote text so I'm =
using three dashes as a delimiter...

---
Clearly you've taken some time with this analysis, and I appreciate
that. I am also not a cryptanalyst, but I do not think I agree with a
---

Thanks!

---
implementation becomes widespread (i.e. is implemented in some sort of
widely-used library) some attackers will begin computing tables of 932
rounds of said hash function ;-).
---

Yes and no. Bear in mind that when people worry about rainbow tables =
they're often thinking of LANMAN hashes and such. Computing complete =
rainbow tables for something like SHA1, especially multiple rounds, is =
still a very big job, and it's defeated by any salt whasoever (in the =
sense that the rainbow table has to be recomputed). Using a distinct =
salt for each hash means that in effect you'd need a different rainbow =
table for each hash.

To my thinking this is a similar mitigation for the entropy issue. It's =
not a complete mitigation, but having to break each hash separately =
slows the attacker down in the case where each hash has a unique salt, =
even if the attacker compromises the salt values. Slows them down =
significantly, but no it does not completely mitigate the attack.

Especially if you consider that a PS3 can compute 2 million MD5 hashes =
per second! =
(http://www.integrigy.com/oracle-security-blog/archive/2007/12/11/hashing=
-credit-card-numbers-again)

---
Regarding symmetric encryption, I am not sure I follow your explanation
...
Put in shorter mathematical terms:
z =3D f(x,y)
x =3D g(z, y)
and
x =3D (g(f,y),y)
---

Yes, this is more accurate, I was simplifying out the key. However I =
wasn't quite saying this. Using your notation, the attack works when:

z =3D f(x, k)
z' =3D f(x, k)

if z =3D=3D z`, then an attacker can use brute force to recover the =
plaintext from the ciphertext. The decryption function g(x,y) is not =
necessary. So if your encryption function always produces the same =
ciphertext for a given plaintext, and the attacker can use you =
encryption function (knows the encryption key), the same attack exists =
as for hashes. This is not always the case (random padding), but for =
those implementations where it is, encryption is vulnerable to the same =
attack as hashing.

---
I would take exception to the statement that the encryption key in
reversible encryption (whether symmetric or asymmetric) need be stored
in the same place as the ciphertext. In the case of an asymmetric key
system in particular, the private key could reside within a business
logic server while the (enciphered) data exists within a database on a
(potentially architecturally different) machine.
---

The bit of my post which was possibly not clear as I was trying to cover =
a lot in a small space was that the attacker has no need for the =
decryption key in the case of assymetric encryption. He can recover the =
plaintext simply by encrypting all possible plaintexts and comparing =
them with the recovered ciphertexts. This only requires knowledge of the =
public encryption key.

Regardless of assymetric / symmetric, the encryption key typically has =
to reside on the server, so that incoming data can be encrypted. =
Symmetric crypto is probably a bad choice for theses kinds of systems, =
since there's no need to use any sort of interesting way of decrypting =
the CC#s ... the key is stored with the data. =20

---
When dealing with symmetric key cryptography which uses a single key to
encipher all CC #'s:

1) The card numbers are readily indexed/compared
2) The entropy problem is fixed. The symmetric key can be created
through secure sampling of 'random' sources for an entropy pool, and
does not depend on data entropy.
3) It is possible to define a format which pads the CC# with random
numbers, and provides an initial-byte index to the start of the real CC
# to protect against partial known plaintext attacks
4) If you use a long, highly random key, and it is not compromised via
other means, it becomes very computationally expensive to brute force =
this
---

1 and 3 can not be simultaneously true. As soon as you add random =
padding (or generate new keys for every plaintext, which would be a =
little crazy), you loose the ability to compare ciphertexts. This is a =
good thing, and was basically the point I was observing in my original =
post. You have the ability to compare encrypted/hashed values, or you =
have security, but it seems very difficult to implement a system that =
has both.

It really doesn't matter a whole lot what algorithm your using to arrive =
at your ciphertext, hash, or whatnot. If the algorithm preserves your =
property 1, and an attacker can compute it (has the encryption key in =
the case of encryption) then he can apply it to all possible plaintexts =
and use comparison with the ciphertext to break the system. There just =
isn't enough entropy in the input.

On the other hand for encryption, and to some extent hashing, by using =
large random padding / salt that's unique for each plaintext, you can =
secure the system. In the case of encryption, since the padding need not =
be stored in the clear, the attack becomes impossible but so does =
comparison (z !=3D z'). In the case of hashing you have the weakness of =
storing the salts along with the hashes, but you could still do =
comparison, although you'd have to rehash the value to compare with each =
distinct salt value.=20

---
However:
1) The key must be stored *somewhere* and may dramatically increase the
chance of compromise
2) All cards are broken at once if the same key is used.
---

As much as Rainbow Tables are the 'big bad wolf' these days, hashing =
does offer the advantage of being irreversible.

I dismiss symmetric encryption out of hand for any system that has to do =
real-time transaction processing because of 1. The key has to be there =
somewhere to encrypt the credit card numbers for new transactions. Sure =
there are probably some convoluted hardware solutions, but in principle =
the key is online with the data.

Assymetric encryption is a great option if you implement it with some =
significant random padding so that an attacker who recovers the public =
key can not encrypt all possible plaintexts and recover the correct one =
by comparison with your compromised ciphertext. Same problem as hashes. =
Add random padding, and you can no longer do comparisons.

---
As I said, I am not a cryptanalyst, so I apologize if I've botched any
of this.
---

Hey it's fun to talk about. There are probably some *real* crypto types =
out there having a good chuckle at our "amateur" discussion, but it's an =
interesting applied problem to think about!=20

(And hopefully someone naively implementing credit card storage will =
read this, and realise that it is far from as simple as picking the =
right magic-bullet function from their crypto library)


Cheers,
~ol

------_=_NextPart_001_01C8D588.04BBAFAE
Content-Type: text/html;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; =
charset=3Diso-8859-1">
<META NAME=3D"Generator" CONTENT=3D"MS Exchange Server version =
6.5.7652.24">
<TITLE>RE: [WEB SECURITY] Hashing and entropy</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/plain format -->

<P><FONT SIZE=3D2>Hi Nathaniel,<BR>
<BR>
Sorry about the quoting, my webmail client doesn't quote text so I'm =
using three dashes as a delimiter...<BR>
<BR>
---<BR>
Clearly you've taken some time with this analysis, and I appreciate<BR>
that. I am also not a cryptanalyst, but I do not think I agree with =
a<BR>
---<BR>
<BR>
Thanks!<BR>
<BR>
---<BR>
implementation becomes widespread (i.e. is implemented in some sort =
of<BR>
widely-used library) some attackers will begin computing tables of =
932<BR>
rounds of said hash function ;-).<BR>
---<BR>
<BR>
Yes and no. Bear in mind that when people worry about rainbow tables =
they're often thinking of LANMAN hashes and such. Computing complete =
rainbow tables for something like SHA1, especially multiple rounds, is =
still a very big job, and it's defeated by any salt whasoever (in the =
sense that the rainbow table has to be recomputed). Using a distinct =
salt for each hash means that in effect you'd need a different rainbow =
table for each hash.<BR>
<BR>
To my thinking this is a similar mitigation for the entropy issue. It's =
not a complete mitigation, but having to break each hash separately =
slows the attacker down in the case where each hash has a unique salt, =
even if the attacker compromises the salt values. Slows them down =
significantly, but no it does not completely mitigate the attack.<BR>
<BR>
Especially if you consider that a PS3 can compute 2 million MD5 hashes =
per second! (<A =
HREF=3D"http://www.integrigy.com/oracle-security-blog/archive/2007/12/11/=
hashing-credit-card-numbers-again">http://www.integrigy.com/oracle-securi=
ty-blog/archive/2007/12/11/hashing-credit-card-numbers-again</A>)<BR>
<BR>
---<BR>
Regarding symmetric encryption, I am not sure I follow your =
explanation<BR>
...<BR>
Put in shorter mathematical terms:<BR>
z =3D f(x,y)<BR>
x =3D g(z, y)<BR>
and<BR>
x =3D (g(f,y),y)<BR>
---<BR>
<BR>
Yes, this is more accurate, I was simplifying out the key. However I =
wasn't quite saying this. Using your notation, the attack works =
when:<BR>
<BR>
z =3D f(x, k)<BR>
z' =3D f(x, k)<BR>
<BR>
if z =3D=3D z`, then an attacker can use brute force to recover the =
plaintext from the ciphertext. The decryption function g(x,y) is not =
necessary. So if your encryption function always produces the same =
ciphertext for a given plaintext, and the attacker can use you =
encryption function (knows the encryption key), the same attack exists =
as for hashes. This is not always the case (random padding), but for =
those implementations where it is, encryption is vulnerable to the same =
attack as hashing.<BR>
<BR>
---<BR>
I would take exception to the statement that the encryption key in<BR>
reversible encryption (whether symmetric or asymmetric) need be =
stored<BR>
in the same place as the ciphertext. In the case of an asymmetric =
key<BR>
system in particular, the private key could reside within a business<BR>
logic server while the (enciphered) data exists within a database on =
a<BR>
(potentially architecturally different) machine.<BR>
---<BR>
<BR>
The bit of my post which was possibly not clear as I was trying to cover =
a lot in a small space was that the attacker has no need for the =
decryption key in the case of assymetric encryption. He can recover the =
plaintext simply by encrypting all possible plaintexts and comparing =
them with the recovered ciphertexts. This only requires knowledge of the =
public encryption key.<BR>
<BR>
Regardless of assymetric / symmetric, the encryption key typically has =
to reside on the server, so that incoming data can be encrypted. =
Symmetric crypto is probably a bad choice for theses kinds of systems, =
since there's no need to use any sort of interesting way of decrypting =
the CC#s ... the key is stored with the data.&nbsp;<BR>
<BR>
---<BR>
When dealing with symmetric key cryptography which uses a single key =
to<BR>
encipher all CC #'s:<BR>
<BR>
1) The card numbers are readily indexed/compared<BR>
2) The entropy problem is fixed. The symmetric key can be created<BR>
through secure sampling of 'random' sources for an entropy pool, and<BR>
does not depend on data entropy.<BR>
3) It is possible to define a format which pads the CC# with random<BR>
numbers, and provides an initial-byte index to the start of the real =
CC<BR>
# to protect against partial known plaintext attacks<BR>
4) If you use a long, highly random key, and it is not compromised =
via<BR>
other means, it becomes very computationally expensive to brute force =
this<BR>
---<BR>
<BR>
1 and 3 can not be simultaneously true. As soon as you add random =
padding (or generate new keys for every plaintext, which would be a =
little crazy), you loose the ability to compare ciphertexts. This is a =
good thing, and was basically the point I was observing in my original =
post. You have the ability to compare encrypted/hashed values, or you =
have security, but it seems very difficult to implement a system that =
has both.<BR>
<BR>
It really doesn't matter a whole lot what algorithm your using to arrive =
at your ciphertext, hash, or whatnot. If the algorithm preserves your =
property 1, and an attacker can compute it (has the encryption key in =
the case of encryption) then he can apply it to all possible plaintexts =
and use comparison with the ciphertext to break the system. There just =
isn't enough entropy in the input.<BR>
<BR>
On the other hand for encryption, and to some extent hashing, by using =
large random padding / salt that's unique for each plaintext, you can =
secure the system. In the case of encryption, since the padding need not =
be stored in the clear, the attack becomes impossible but so does =
comparison (z !=3D z'). In the case of hashing you have the weakness of =
storing the salts along with the hashes, but you could still do =
comparison, although you'd have to rehash the value to compare with each =
distinct salt value.<BR>
<BR>
---<BR>
However:<BR>
1) The key must be stored *somewhere* and may dramatically increase =
the<BR>
chance of compromise<BR>
2) All cards are broken at once if the same key is used.<BR>
---<BR>
<BR>
As much as Rainbow Tables are the 'big bad wolf' these days, hashing =
does offer the advantage of being irreversible.<BR>
<BR>
I dismiss symmetric encryption out of hand for any system that has to do =
real-time transaction processing because of 1. The key has to be there =
somewhere to encrypt the credit card numbers for new transactions. Sure =
there are probably some convoluted hardware solutions, but in principle =
the key is online with the data.<BR>
<BR>
Assymetric encryption is a great option if you implement it with some =
significant random padding so that an attacker who recovers the public =
key can not encrypt all possible plaintexts and recover the correct one =
by comparison with your compromised ciphertext. Same problem as hashes. =
Add random padding, and you can no longer do comparisons.<BR>
<BR>
---<BR>
As I said, I am not a cryptanalyst, so I apologize if I've botched =
any<BR>
of this.<BR>
---<BR>
<BR>
Hey it's fun to talk about. There are probably some *real* crypto types =
out there having a good chuckle at our &quot;amateur&quot; discussion, =
but it's an interesting applied problem to think about!<BR>
<BR>
(And hopefully someone naively implementing credit card storage will =
read this, and realise that it is far from as simple as picking the =
right magic-bullet function from their crypto library)<BR>
<BR>
<BR>
Cheers,<BR>
~ol<BR>
</FONT>
</P>

</BODY>
</HTML>
------_=_NextPart_001_01C8D588.04BBAFAE--