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

Groups > comp.lang.forth > #19544

Re: OT: HTTPS cracked

Show all headers | View raw

Bernd Paysan <bernd.paysan@gmx.de> writes:
> Related key attacks are indeed indirect attacks, but there are often 
> cases where you have poor entropy in the system that generates the keys.  

If your RNG is broken, you have far worse problems than some theoretical
O(2**100) related key attack on the block cipher.  Really.

> As Schneier puts it, cryptosystems are rarely directly broken, but most 
> often circumvented.  This TLS attack here is just another case.

Sure.  The guys who designed SSL in the 1990's were pretty smart, but
they were operating by intutition and head-scratching.  These days we
have more powerful methods for validating protocols, so we would
do things differently.  Unfortunately TLS is just some minor patches
on SSL rather than a redesign, so things keep going wrong.

> In any case, if you have a related key problem, you must choose your 
> keys so that they are unrelated.  This reduces the possible space to 
> choose keys from, and thus also reduces the strength of the algorithm.  

This is not a significant effect unless the related key families
are enormously large.  Consider the DES key complementation property,
which says E(K,X) = ~E(~K,~X) if I remember properly.  That is, every
key is paired with its complement to relate plaintexts in a trivial
way.  So a key search would check the ciphertext and its complement
at the same time, thus the property destroys a full bit of the search
space.  This has been known since the 1970's and basically nobody cares.
The effect of related keys on search space would have to be far worse
to matter.

> using a good secure random number generator is sufficient to give you 
> all the unrelated keys you need.

Right, this is why related keys aren't a standard security criterion
(of course too many of them do start impacting the standard criteria).

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

I've located the paper but haven't had a chance to read it yet, so I
don't know what the above sentence means.

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

AFAIK, AES only makes one claim, that it can't be feasibly distinguished
from a random permutation.  It doesn't make claims about related keys.

> The broad claims of Rijndael weren't met. 

Yeah but I don't see much of a problem there.  Slashdot car analogy: 

1. NIST creates a competition for the Advanced Automotive Standard
(AAS), inviting car designs that meet various specifications about how
the car must operate on different types of roads.  

2. The Rijndael guys decide they can design a car that does the required
stuff, and hey wouldn't it be cool if their car also worked underwater?
They claim their car does all the NIST stuff, even under 256 feet of
water.  The success of any of these claims has not yet been determined.

3. NIST says "this competition is for above ground performance, we don't
care about underwater since current prevailing practice is to use
submarines for that."  Rijndael and other cars compete in a grueling
series of above-ground tests and Rijndael wins.  There are no underwater
tests in this process.  Nobody else has even considered making their car
go underwater, or takes Rijndael's claim terribly seriously (though it
would be cool if it really works).

4. Years later, someone devises an intricate way to make the Rijndael
car fail under 100 feet of water instead of the advertised 256 feet.

Really, the previous standard (DES) per the key complementation
property, failed catastrophically in a trivial way, under just 1 foot of
water (1 bit).  When the car is used as intended, this is simply not a
problem.  If the car really was expected to work underwater, various
operational modes could be deployed that used this capability (e.g.
signcryption modes could be more efficient) instead of relying on
separate vehicles.  But observably, nobody uses those modes, because
they knew better to really believe in the underwater car beyond thinking
that it was a neat idea.

If Rijndael were really an ideal cipher, it could trivially be used as a
"tweakable" cipher at no cost in speed.  I'm not really conversant with
the topic but I think tweakable cipher designs tend to add extra rounds.
Therefore, someone with a tweakable cipher considering entering the AES
contest would probably want to remove a few rounds to gain speed, in
exchange for giving up the tweakability which was not part of the
contest.

> The general attitude at cryptography is that any algorithm that doesn't 
> meet its claims is considered broken, even if the attacks are not (yet) 
> practicable.  

Sure, but I haven't seen any attacks that break any of AES's claims.
The attack we're discussing breaks a relatively untested Rijndael claim,
not the very thoroughly tested AES claims.  But, I may soon get a chance
to ask some crypto specialists about any new developments, so I'll try
to do that.

> That's what NIST did with starting a new round on hashes,

Yeah, I have to say though that the design problems for hash functions
(that don't use any secrets) are different and harder than those for
block ciphers.  There are mathematical reasons why hash functions have
had worse attacks than AES over the years.

> but they only started it when MD5 was too weak to be used any longer,

Maybe you mean SHA1.

> IMHO, the whole approach of block ciphers is problematic.  You want a 
> pseudo-random function that is bijective,

Right, a pseudorandom permutation (PRP), not a PRF.  But per the
switching lemma, up to the birthday bound, a PRP and a PRF are the same
thing.

> not such a big problem, but one of the reasons why you should not
> easily use AES as primitive for a known-key hash is that you can
> always work your way backwards, it's not a one-way function. 

Really, that's not it.  PRP's and PRF's both depend on having a secret
key, and the absence of a secret key is what makes hashing so hard.  A
PRF makes a perfectly good stream cipher.  I don't know the timings for
Keccak, but I'll hazard a guess that it's slower than the
best-performing stream ciphers.  The absence of a secret key gives it
more work to do.  Unlike a PRP or PRF, it's hard to even write down a
mathematical definition of a secure hash function.

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