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

Groups > comp.lang.forth > #19622

Re: OT: HTTPS cracked

Show all headers | View raw

Paul Rubin wrote:
> 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.

Well, it's probably a combination of somewhat weak keys and the related key 
attack:  You occasionally walk on keys that make it particularly easy to do 
the related key attack.

AES-128 and AES-196 have no similar weaknesses; it's simply the key 
expansion on AES-256 is insufficient.

>> 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.

Actually, for today's standard, AES is pretty slow.  A lot slower than 
ciphers which are much closer to "ideal".

> So we instead use modes and protocols that don't
> require the property.

Yes, we work around the flaws of AES in modes and protocols, and by looking 
at how many times people fail on that, this approach just doesn't work.

>> 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.

RC4 is a pretty simple and rather ancient stream cipher, and has lots of 
weaknesses.

> 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.

A number of stream ciphers are completely happy when the block key is 
unique.  Just as a general rule: If there is a distinguisher from randomness 
which needs less effort than an exhaustive search, a cipher is considered 
broken; though workarounds may exist that allow to still use the cipher 
without practical impacts.  It's still broken.

The test suite for a good stream cipher is quite easy: Any next state must 
be completely unrealted to the previous state.  I.e. if you just flip a bit 
in one state, the next state must be completely unrelated.

We have severe related key issues with RC4, and a distinguisher needs ony 
2^25 bytes (Paul & Preneel).  I'm not interested in discussing known crappy 
ciphers.  Yes, RC4 is just "the other option" in TLS...  It doesn't help on 
the padding oracle attacks (in RC4, there is no padding, so you don't need 
an oracle, you just look at the length ;-)...

>> 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.

Any reasonable algorithm can only require one spec: The keys have to be 
secret.  The rest shouldn't matter, because you are reducing your key space, 
and the key space of AES-128 clearly is not big enough to require a Hamming 
distance of ~64 bits between the keys you can use.

I've already stated that I consider the whole spec for AES as inadequate.  
Starting with "should be a block cipher with ECB mode".  Nobody needs ECB, 
so this is simply something you should not write in your requirements.  It's 
like a Formula 1 car is specified as "cabrio", which means the helmet sticks 
out, and while that is complete nonsense (nobody wants a cabrio to drive at 
350km/h), and drivers have been killed due to that fact, that's still in the 
spec.

>> 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.

Yes, but that's a constraint that is completely useless.  It's like "you 
have to jump through this ring of fire, with your feets tied together".  
Why?  Jump trough the ring of fire without that constraint, and it's a piece 
of cake.

> 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.

Cool, interesting, and *wrong*.  Please, if an engineer makes bold and wrong 
claims about things he does, he loses credibility, and right so.

>> 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?

Pseudo-random, and the reverse function should be NP-hard, i.e. you need an 
exhaustive search through the input range to find which input creates a 
particular output.  The analysis about "how many rounds do I need" in Keccak 
or Salsa20 are based on how difficult it is to reverse one round (usually 
not that difficult), and how much combinatoric explosion you add by further 
rounds.  This is all guestimate, as we even can't prove that P!=NP.

Unrelated just means that: there is no known relation in P which gets you 
back from the output to the input state.  It's a pretty mathematical 
"unrelated".  There is a pretty cheap relation from input -> output, it's 
the actual transfer function or permutation of the crypto primitive.

> 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.

Yes, it's missing that the reverse function must be hard.  If you use AES 
with a known key for e.g. CBC-MAC, you get this pseudo-random property, but 
the reverse funktion is actually trivial.  If your last message block is 
free to choose, you can forge whatever message you like to give a certain 
CBC-MAC checksum.  This comes from having a reversible permutation function 
as core of the cipher (which it must be, because it is a block cipher).

> 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.

Thanks for the link, I'll read it...  You should remember that I'm not an 
English native speaker, and all the terminology I learned at TU Munich was 
deliberately German.  The stuff there certainly helps me to understand the 
terminology you use.

It looks a bit dated, most of the stuff has been written a decade ago.  In 
essence, it does not contain any of the techniques I use.  No ellyptic curve 
cryptography, no sponge functions, nothing.  The slides about PKI don't 
mention the breakdown of the SSL PKI (instead, it gives the impression that 
the CA system is good).

I simply consider AES to be not adequate for what I'm doing.  Accept that 
fact.  I might not convince you to abandon AES, but I don't like it, if 
anything, it at least is too slow unless AES-NI is used.  You can't force 
anyone using an algorithm he doesn't feel comfortable with.  It simply does 
not meet *my* requirements.  An I consider block ciphers to be a not very 
clever approach at encryption.  They have been state of the art for a long 
time, though.  This doesn't mean that they are a good idea.  The history of 
encryption is a history of mistakes.

The key issue I have is that I need fast encrypt+authentication, and block 
ciphers don't have a one-stop solution for that (E+A, as the linke above 
says, is insecure in general on a block cipher, and if you can make it work, 
it is so by using a workaround), and the two-stop solutions are pretty slow, 
if you don't use some hardware implementation like AES-NI.  The fact that 
about every protocol I know of got it wrong one way or the other is telling.

If you use e.g. a sponge function that is known good for a secure hash, you 
don't have any of these problems.  The sponge function gives you encryption 
and a keyed hash, which is perfect for authentication, all in one go (you 
can't compute the hash without knowing both key and plaintext, and you can't 
forge a message to match a hash, even when you knew the key).  That's 
relatively recent research; it soon will go into the text books, since 
Keccak is now SHA-3.

As I'm using Forth, I value versatility *and* simplicity.

BTW: AES being inadequate doesn't mean "I will never implement it as an 
option in net2o".  The generic crypto API in net2o allows you to plug in 
anything that can securely encrypt pre-padded blocks (padded to multiple of 
64 bytes, with zeros) and add a 128 bit MAC.  There is one good reason to 
use AES on new Intel processors, as with AES-NI, it is fast and compact; 
something you can't say of AES in software.  AES-NI pushes you to use GCM as 
MAC, so in essence, this fixes the mode.

The big difference between cryptography as explained in the introduction by 
the link you gave - which is for online banking and such - and cryptography 
in a modern Internet today is that the latter is to protect your privacy and 
freedom, your privacy when sharing pictures of cats and food, and your 
freedom by protecting you from the authorities when you spread the news of 
corrupt officials in China, when you access information that is censored in 
your country, or download a movie in the USA (the latter is punished harder 
than the first one; when you actually anger politicians in the US, they want 
to kill you).  This is why it needs to be ubiquitous, and this is why it 
needs to be fast and slim.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

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