Prev: JSH: Why being right isn't enough
Next: Double encryption method
From: Kristian Gj�steen on 16 Jun 2010 04:10
Paul Rubin <no.email(a)nospam.invalid> wrote:
>I don't understand Francois Grieu's random oracle proof well enough to
>say I'm convinced by it. That doesn't mean I think it's wrong, but I
>have reservations about it. I don't see how any results about random
>oracles applies when the key is known. It's not an oracle at all, since
>the cipher's complete internal state is available through every step of
>the algorithm.

The same holds for hash functions as well, so this is not an objection
against random oracle arguments.

The idea is that the adversary doesn't really care about the internals
of the function, and the function should be a typical example of a
"random function" (or "random permutation").

Once you believe that about aes(k,.), the argument should be plausible.

--
Kristian Gj�steen
From: Francois Grieu on 16 Jun 2010 06:23
On 16/06/2010 03:06, Maaartin wrote:
> I'd like to conclude:
>
> - Using H(x) = x ^ aes(k, x) for a fixed known k is a secure hash as
> long as aes is secure.
>
> - (..snip..)
>
> - It's probably faster then md5(x) and there's no reason to believe
> it's less secure.
>
> Does everybody agree?

Yes, with no practical reservation, but two remarks:

1) Making a hash faster makes brute force proportionally faster, and
less unlikely to succeed.

2) For an adversary with unbounded memory, finding a preimage to
H(x) = x ^ aes(k, x) for some known constant k
with a given odd of success requires on average slightly less
evaluations of aes than would
H(x) = aes(x, c) for some known constant c
but that gain is by a factor of at most two, and entirely negligible for
an adversary with a practical amount of memory.
The security bounds obtainable for the two constructs under a random
oracle model reflect this fact. In practice, the improvement is possible
because computing y = aes(k, x) and verifying that x ^ y is not the
desired h, is enough to rule out both x and h ^ y as possible solutions.

Francois Grieu
From: Thomas Pornin on 16 Jun 2010 07:45
According to Maaartin <grajcar1(a)seznam.cz>:
> H(x) = x ^ aes(k, x)
[...]
> - It's probably faster then md5(x)

On an Intel Core 2 (Q6600), it takes about 375 clock cycles to process
one MD5 block; that's the base cost of hashing any message up to 55
bytes. On the same machine, OpenSSL's implementation of AES/CBC
processes one block (i.e. one AES and one XOR) in about 230 clock
cycles(*). So the H() function above is indeed faster than MD5 on 16-byte
input, but:
- not by a large margin;
- the timings may be different on other architectures;
- the AES implementation uses tables (cumulative size is 4 kB) so it
needs some L1 cache, which MD5 does not; this may or may not change
things, possibly drastically, depending on the rest of the application
(the code which uses that H() function).

Hence it is relatively unclear whether H() is always faster than MD5. It
seems plausible that H() and MD5 will offer performance of similar
magnitude on most systems, except those for which either AES or MD5
benefits from some specialized hardware.


--Thomas Pornin

(*) There is a paper by Bernstein and Schwabe which claims about 169
clock cycles for an AES block, and the XOR will account for no more than
4 extra clock cycles, so that "230" could be reduced to something like
"173". But remember that this is in "ideal benchmark conditions",
something which rarely happens in actual applications, especially due to
cache effects: the L1 cache (both instruction and data) must be shared
with the rest of the code in the data processing path.
From: Francois Grieu on 16 Jun 2010 08:17
On 16/06/2010 03:43, Paul Rubin wrote:
> I don't understand Francois Grieu's random oracle proof well enough to
> say I'm convinced by it. That doesn't mean I think it's wrong, but I
> have reservations about it. I don't see how any results about random
> oracles applies when the key is known. It's not an oracle at all, since
> the cipher's complete internal state is available through every step of
> the algorithm.

Kristian Gj�steen made a fine answer; I'll try my own: The random oracle
model for a cipher restricted to randomly chosen known constant key
makes sense; it is also the random oracle model for a randomly chosen
permutation.

Francois Grieu
From: Maaartin on 16 Jun 2010 10:47
> On 16/06/2010 03:06, Maaartin wrote:
> > Does everybody agree?
>
> Yes, with no practical reservation, but two remarks:
>
> 1) Making a hash faster makes brute force proportionally faster, and
> less unlikely to succeed.

I understand "faster", and don't care much - what is factor 10 (which
is much more then I can get) when doing something impossible? I don't
understand "less unlikely", except when you mean "less unlikely in
given time".

> 2) For an adversary with unbounded memory, finding a preimage to
> H(x) = x ^ aes(k, x) for some known constant k
> with a given odd of success requires on average slightly less
> evaluations of aes than would
> H(x) = aes(x, c) for some known constant c
> but that gain is by a factor of at most two, and entirely negligible for
> an adversary with a practical amount of memory.
> The security bounds obtainable for the two constructs under a random
> oracle model reflect this fact. In practice, the improvement is possible
> because computing y = aes(k, x) and verifying that x ^ y is not the
> desired h, is enough to rule out both x and h ^ y as possible solutions.

Ok, this helped me understand it better.

On Jun 16, 1:45 pm, Thomas Pornin <por...(a)bolet.org> wrote:
> According to Maaartin <grajc...(a)seznam.cz>:
>
> > H(x) = x ^ aes(k, x)
> [...]
> > - It's probably faster then md5(x)
>
> On an Intel Core 2 (Q6600), it takes about 375 clock cycles to process
> one MD5 block; that's the base cost of hashing any message up to 55
> bytes. On the same machine, OpenSSL's implementation of AES/CBC
> processes one block (i.e. one AES and one XOR) in about 230 clock
> cycles(*). So the H() function above is indeed faster than MD5 on 16-byte
> input, but:
> - not by a large margin;
> - the timings may be different on other architectures;
> - the AES implementation uses tables (cumulative size is 4 kB) so it
> needs some L1 cache, which MD5 does not; this may or may not change
> things, possibly drastically, depending on the rest of the application
> (the code which uses that H() function).
>
> Hence it is relatively unclear whether H() is always faster than MD5. It
> seems plausible that H() and MD5 will offer performance of similar
> magnitude on most systems, except those for which either AES or MD5
> benefits from some specialized hardware.
>
> --Thomas Pornin
>
> (*) There is a paper by Bernstein and Schwabe which claims about 169
> clock cycles for an AES block, and the XOR will account for no more than
> 4 extra clock cycles, so that "230" could be reduced to something like
> "173". But remember that this is in "ideal benchmark conditions",
> something which rarely happens in actual applications, especially due to
> cache effects: the L1 cache (both instruction and data) must be shared
> with the rest of the code in the data processing path.

This is sad. The fastest thing I've found is a bit-sliced
implementation (by Kaesper and Schwabe) using SSE3 and achieving 7.08
cycles per byte on Intel Core i7 920 when processing 4KiB. Even so,
this means 114 cycles for an AES block and speedup factor of three
only. It uses no tables, but it achieves the speed for large blocks
only. I don't think I could get anywhere close even if I could rely on
SSE3.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8
Prev: JSH: Why being right isn't enough
Next: Double encryption method