Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #19602

Re: OT: HTTPS cracked

Show all headers | View raw

Bernd Paysan <bernd.paysan@gmx.de> writes:
>>> The current state of this related-key attack is that you can crack
>>> one out of every 2^35 (randomly chosen?) keys with a complexity of
>>> 2^96.

Again I'm not sure exactly what the above means (I still have to read
the paper).  If you're saying that any random pair of AES-256 keys have
a 2**-35 chance of being related in a way that can be detected with
around 2**96 work, then that counts as a break against AES-256.  Given a
permutation oracle that might be AES-256 or might be random, generate a
random AES-256 instance and try the related-key attack.  If the attack
succeeds with 2**-35 probability then that counts as a distinguisher,
breaking the claim that AES-256 is a PRP.  But, maybe the attack is
something different than this.

>>> The whole thing about AES is that "it somehow works if a number of
>>> conditions is met".

Well the conditions are not complicated, and they are stated in a
very precise way.

> I would expect from any cryptosystem that a related key results in a 
> totally unrelated cipher stream.

That's not a valid expectation for standard primitives like AES.  A
cipher with that property is called an "ideal cipher" and designing for
it costs performance.  So we instead use modes and protocols that don't
require the property.

> E.g. a stream cipher has the property that you are allowed to use each
> key only *once*.  

No.  The designers of WEP thought something that about RC4, because they
were clueless.  It's not enoguh that the keys be unique.  You are
supposed to choose each key RANDOMLY, independently of any other keys.
It'e the same way with AES.  Someone who doesn't understand that
shouldn't be building applications out of primitives.

> So a perfectly valid approach is to have a shared secret... which you
> increment for each use. 

No, that's a totally INVALID approach unless the primitive was specified
for that mode, which AES was not.  AES keys are supposed to be random
and independent.

> You can do it with many other stream ciphers, like Salsa20, or Keccak
> in stream cipher mode, or whatever, it doesn't break anything. 

Swell, that does make some applications simpler.  On the other hand,
Salsa20 and Keccak are not block ciphers, so there are some other
constraints that AES has to deal with, but stream ciphers don't.

>> even under 256 feet of water...
> Cryptography requires correct analysis.  When the submitter make bold 
> claims that turn out to be wrong, the quality of their analysis is in 
> doubt.  That's bad engineering.

The test was the AES competition and Rijndael beat all the other
entrants at meeting the AES specs.  That's the best we can hope for
with the current state of knowledge.  The non-AES claims weren't
part of the AES submission and nobody took them very seriously.
They were just cool and interesting aspects of the cipher.

>> (DES) per the key complementation property, failed catastrophically
>> in a trivial way, under just 1 foot of water (1 bit).
> Come on, DES was not even chosen from a contest.  The reasons why to 
> choose DES' S-box were kept secret, developed by the NSA.

That has nothing to do with the key complementation property, whose
operation is obvious from DES's design.  The point of mentioning it
is that DES users knew about it for 30+ years and didn't care.  They
just used DES in a way that wasn't affected by it.

> Well, the 2 bits shaved off AES strength are actually attacks at AES's 
> claims, not Rijndael's.

Hmm. If that's off AES-256 and doesn't really bring out anything new,
then it doesn't seem like a cause for concern.  We saw similar things
over the history of DES but eventually it was the limited key space and
block size that obsoleted DES.

>> it's hard to even write down a mathematical definition of a secure
>> hash function.
>
> You should read the Keccak paper.  They do have a mathematical 
> definition, and their benchmark is "random oracle". 

Random oracles are a mathematical model useful for studying some
protocols that incorporate secure hashes, but they're not a definition
of a secure hash.  In particular, the only way to find the output for a
given input to a random oracle is to actually query the oracle.  Random
oracles can model PRF's (because you don't know the secret key), but for
a keyless hash, you can just have a separate implementation of the hash
function and learn hash outputs without making any oracle queries.

> I.e. the transfer/permutation function must produce an unrelated
> output from any input (the total state of the sponge function), 

And you define an "unrelated output" exactly how?

IIRC, krawczyk's HMAC paper relies on the hash having the property that
for a secret key K and fixed message size N, the function

  F(M) = Hash(K || M)

is pseudorandom, for messages M of size N.  But, I think that is not
considered a satisfactory definition.  I had a discussion about this
with a crypto professor on sci.crypt some years back and it sort of
fizzled out.  Later I learned there is a complicated theory of entropy
extractors which I think gets a bit closer, but I'm not sure.

The main reference I know of about low level security definitions is the
2-volume "Foundations of Cryptography" by Oded Goldreich.  There's an
early draft online but I haven't had the motivation to try reading it in
a serious way.

I really liked Bellare and Rogaway's lecture notes on cryptography
and I'd urge you to read them, at least the first few chapters:

  http://cseweb.ucsd.edu/users/mihir/cse207/classnotes.html

They are more readable than the Goldreich book and the demystified the
subject a lot for me.  I think you're currently under some
misconceptions that come from using an insufficiently mathematical
approach to the subject, and the notes above should help fix that.
They'll at least improve the quality of the discussion we're having.

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

OT: HTTPS cracked Mark Wills <forthfreak@gmail.com> - 2013-02-05 02:59 -0800
  Re: OT: HTTPS cracked Mark Wills <forthfreak@gmail.com> - 2013-02-05 03:01 -0800
    Re: OT: HTTPS cracked Alex McDonald <blog@rivadpm.com> - 2013-02-05 06:29 -0800
      Re: OT: HTTPS cracked Bernd Paysan <bernd.paysan@gmx.de> - 2013-02-05 18:16 +0100
        Re: OT: HTTPS cracked Paul Rubin <no.email@nospam.invalid> - 2013-02-05 09:53 -0800
          Re: OT: HTTPS cracked Bernd Paysan <bernd.paysan@gmx.de> - 2013-02-05 22:43 +0100
            Re: OT: HTTPS cracked Paul Rubin <no.email@nospam.invalid> - 2013-02-06 05:00 -0800
              Re: OT: HTTPS cracked Bernd Paysan <bernd.paysan@gmx.de> - 2013-02-06 19:21 +0100
                Re: OT: HTTPS cracked Paul Rubin <no.email@nospam.invalid> - 2013-02-08 01:06 -0800
                Re: OT: HTTPS cracked Bernd Paysan <bernd.paysan@gmx.de> - 2013-02-08 17:23 +0100
                Re: OT: HTTPS cracked Paul Rubin <no.email@nospam.invalid> - 2013-02-09 20:04 -0800
                Re: OT: HTTPS cracked Bernd Paysan <bernd.paysan@gmx.de> - 2013-02-11 02:56 +0100
      Re: OT: HTTPS cracked the_gavino_himself <visphatesjava@gmail.com> - 2013-02-08 19:27 -0800

csiph-web