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

Groups > comp.lang.forth > #19449 > unrolled thread

OT: HTTPS cracked

Back to article view | Back to comp.lang.forth

Contents

  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

#19449 — OT: HTTPS cracked

http://www.theregister.co.uk/2013/02/04/unlucky_13_crypto_attack/

[toc] | [next] | [standalone]

#19450

On Feb 5, 10:59 am, Mark Wills <forthfr...@gmail.com> wrote:
> http://www.theregister.co.uk/2013/02/04/unlucky_13_crypto_attack/

The method used seems quite tenous to me...

[toc] | [prev] | [next] | [standalone]

#19460

On Feb 5, 11:01 am, Mark Wills <forthfr...@gmail.com> wrote:
> On Feb 5, 10:59 am, Mark Wills <forthfr...@gmail.com> wrote:
>
> >http://www.theregister.co.uk/2013/02/04/unlucky_13_crypto_attack/
>
> The method used seems quite tenous to me...

(Technically it's TLS they broke.) The problem has been known about
for over a decade. The advice is to use code that is slow to run; see
scrypt https://tools.ietf.org/html/draft-josefsson-scrypt-kdf-00 for a
standardised mechanism for this that is prohibitively slow to use for
the repeated attempts that all these cracks require.

[toc] | [prev] | [next] | [standalone]

#19470

Alex McDonald wrote:

> On Feb 5, 11:01 am, Mark Wills <forthfr...@gmail.com> wrote:
>> On Feb 5, 10:59 am, Mark Wills <forthfr...@gmail.com> wrote:
>>
>> >http://www.theregister.co.uk/2013/02/04/unlucky_13_crypto_attack/
>>
>> The method used seems quite tenous to me...

In general, a cryptographic algorithm is considered "broken" when it is 
easier to crack it than a pure brute force attack (i.e. a 128 bit AES 
key is broken when you need less than 2^127 tries for a 50% chance to 
break it).

AFAIK, AES itself is cryptanalized to have only 100 bits in strength 
(both AES-128 and AES-256, the more bits in the key gain nothing); 
though that attack would be impractical (2^100 tries).

> (Technically it's TLS they broke.)

Yes, i.e. the particular use of AES-CBC with SHA1-MAC together with the 
compression used in TLS, and the way they do the padding.

The compression in TLS itself should be removed, it is a problem on 
itself.  One of these attacks is to have the attacker induce a known 
plaintext into the, let's say HTTP command, and use the compression to 
guess what's the cookie, e.g. by making the client send requests to 
Facebook.  The requests contains a referrer (controlled by the 
attacker), and the cookie, and when there's a common substring in the 
cookie and the referrer, the request will be shorter.

The problem is: Padding doesn't help, because you can make the referrer 
arbitrary long, and cause it to cross a block boundary.  So your request 
might be one or two blocks long, depending on whether there was a match 
or not between cookie and referrer string.

The advice I take from the TLS problems (for net2o) is:

* Don't compress on the fly - especially not the commands
* Use pubkey authentication; don't ever transmit shared secrets 
(cookies, passwords) over the net
* Don't use highly variable block sizes, the length is an indication
* Use crypto primitives that offer encryption and authentication in one 
go (sponge functions)
* Generate the keys+ivs out of the shared secret on both sides, rather 
than transmitting them, or worse, deriving them from previous blocks 
(and by doing so, opening up an attack vector)
* Make sure the protocol itself doesn't require particular padding

The attack described here is a timing attack against padding. Padding is 
needed if your original protocol uses the packet length as information 
how long the data string is.  With a block cipher, you can't do that, so 
you need to pad the block in a way that lets you strip off the padding 
at the receiver.  The padding scheme I would use in such conditions is 
that the last byte of the last block should be the size of the data in 
the last block (from 0 to blocksize-1).  That's constant size and 
stripable; it adds another byte to the data.

Much better is when your encrypted data contains the length of all 
strings inside, and those lengths are encrypted, too.  Then you don't 
need to care about the packet length, and you can pad with whatever 
garbage you like.

I think the main problem with SSL is that nobody would do it that way 
today, but it is everywhere, and once a system is widespread enough, you 
can't even add small workarounds, because one client or another will 
fail on that.

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

[toc] | [prev] | [next] | [standalone]

#19474

Bernd Paysan <bernd.paysan@gmx.de> writes:
> AFAIK, AES itself is cryptanalized to have only 100 bits in strength 
> (both AES-128 and AES-256, the more bits in the key gain nothing); 

You mentioned that before, in another post that I've been wanting to get
around to replying to.  Do you have a cite?  I haven't heard such a low
number before, and since AES is a product cipher with the 256-bit
version having a higher number of rounds, it makes no sense to me that
the attack could have the same complexity regardless of the key size.

[toc] | [prev] | [next] | [standalone]

#19484

Paul Rubin wrote:

> Bernd Paysan <bernd.paysan@gmx.de> writes:
>> AFAIK, AES itself is cryptanalized to have only 100 bits in strength
>> (both AES-128 and AES-256, the more bits in the key gain nothing);
> 
> You mentioned that before, in another post that I've been wanting to
> get around to replying to.  Do you have a cite?

Wikipedia directs me here, but I'm not sure if that's the full paper:

http://www.ma.rhul.ac.uk/~sean/rijn_newobs.pdf

They base on Courtois and Pieprzyk work, but some people think that work 
is flawed.  The idea is to obtain a set of quadratic equations from the 
AES algorithm.  This one reduces AES-128 to 2^100.

> I haven't heard such a
> low number before, and since AES is a product cipher with the 256-bit
> version having a higher number of rounds, it makes no sense to me that
> the attack could have the same complexity regardless of the key size.

The key expansion of AES 256 is a weakness.  There's a paper of Alex 
Biryukov and Dmitry Khovratovich for related key attacks, and that one 
estimates that AES-256 has even "only" 2^99.5 bits worth of security 
(half a bit less than AES-128).  It's still way beyond a feasible 
attack, and the attack vector is not practicable, as it is a related key 
attack (you don't know the key, but you know how they relate).

http://cryptolux.uni.lu/mediawiki/uploads/1/1a/Aes-192-256.pdf

FAQ:

https://cryptolux.org/FAQ_on_the_attacks

The only really practical result of this attack is that AES-256 can't be 
used as secure hash function, while AES-128 still can, though of course, 
AES can only savely be used as hash function (with known key) if you 
implement it wide-pipe, which means you get a 64 bit hash out (general 
weakness of any Merkle-Dangard construct).  With unknown key, you can 
use the full 128 bits; that's why CBC-MAC must use a secret key (and not 
the same as the one you use for encryption).

The problem with all these impractical attacks is that they all show 
weaknesses in the construct, which, when combined with other, new 
weaknesses, could make it fall apart.

The point about more modern cryptoprimitives like Keccak or Wurstkessel 
is that bits are cheap.  Keccak uses 1600 bits for its internal state, 
Wurstkessel 1024.  The strength of both is related to the residual bits 	
(those bits that are not used for xoring the plain text), which are a 
minimum of 512 bits for both.  Even if there is a way to reduce the 
complexity of the permutation function, these 512 bits give ample 
headroom.  Both can be used as truly universal primitive, i.e. prng, 
hash, encrypt/decrypt+mac.  Unfortunately, I have only two of those, and 
one of them (Wurstkessel) hasn't gone through peer review.  In general, 
it should be possible to take any good stream cipher core (e.g. salsa20, 
but not rc4), and convert it into a sponge function.

Having more bits helps even when your construction is theoretically 
weak, just look at the hashes: MD5, SHA-1, SHA-256, and SHA-512 have 
essentially the same structural weakness.  MD5 is toast, SHA-1 is sort-
of weak, but both SHA-256 and SHA-512 just have enough bits to be 
strong, despite the same structural weakness applies.

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

[toc] | [prev] | [next] | [standalone]

#19506

Bernd Paysan <bernd.paysan@gmx.de> writes:
> http://www.ma.rhul.ac.uk/~sean/rijn_newobs.pdf

This is old and well known and AFAIK nothing came of it.

> http://cryptolux.uni.lu/mediawiki/uploads/1/1a/Aes-192-256.pdf

This link doesn't work, it goes to an empty wiki page.

> https://cryptolux.org/FAQ_on_the_attacks

I think the FAQ says enough that I understand basically what happened,
and it's not surprising.  It's also not a valid attack against AES,
since the security property that it breaks is one that AES doesn't claim
to have in the first place.  It does appear to be a valid attack against
Rijndael, since while Rijndael is the exact same algorithm as AES, its
designers made broader claims for it than NIST makes for AES.  This
attack is a break against one of those broader claims.  I think it has
been known for a relatively long while too, that those claims didn't
really hold up.  The original claim was that Rijndael was an "ideal
cipher" which meant (e.g.) that it shouldn't have related-key attacks.
That goes considerably beyond what NIST wanted from AES, and is harder
to do.

AES claims to be a pseudorandom permutation, which means it's broken if
you've got a way to distinguish a single instance (using a random key)
from a true random permutation.  The security of all the standard and
not-so-standard modes of operation can be deduced from this property.
Even small families of outright weak keys (like DES's) wouldn't directly
affect AES's security claim.  It would be interesting and somewhat
disconcerting if they were found, of course.

DJB's paper about NaCL is pretty recent and gives a much higher security
figure than 2**100 for AES-256.  It might have said 2**240 or something
like that; I don't have it in front of me.

[toc] | [prev] | [next] | [standalone]

#19512

Paul Rubin wrote:
> AES claims to be a pseudorandom permutation, which means it's broken
> if you've got a way to distinguish a single instance (using a random
> key)
> from a true random permutation.  The security of all the standard and
> not-so-standard modes of operation can be deduced from this property.
> Even small families of outright weak keys (like DES's) wouldn't
> directly
> affect AES's security claim.  It would be interesting and somewhat
> disconcerting if they were found, of course.

Related key attacks are indeed indirect attacks, but there are often 
cases where you have poor entropy in the system that generates the keys.  
As Schneier puts it, cryptosystems are rarely directly broken, but most 
often circumvented.  This TLS attack here is just another case.

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.  
Enough bits keep you safe, so this is not necessarily a practical 
problem - you don't need that many different keys in your lifetime, so 
using a good secure random number generator is sufficient to give you 
all the unrelated keys you need.

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.  
The other keys are considerably harder.

> DJB's paper about NaCL is pretty recent and gives a much higher
> security
> figure than 2**100 for AES-256.  It might have said 2**240 or
> something like that; I don't have it in front of me.

The whole thing about AES is that "it somehow works if a number of 
conditions is met".  The broad claims of Rijndael weren't met.  Looking 
at the other AES finalists makes it hard to choose something better, 
though ;-).

If you have unrelated keys, you can only deduce two bits of the keys 
with practical attacks.  You can deduce some more with impractical 
attacks.

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.  This is a sound attitude, though we certainly have 
examples where first successes didn't lead to more damage (like on 
SHA-1, which did not completely break down, while MD5 did).

Therefore, if you already use that algorithm, you can continue to use it 
as long as the attacks are not practicable, but you need to add another 
option.  That's what NIST did with starting a new round on hashes, but 
they only started it when MD5 was too weak to be used any longer, and 
therefore, the concerns were really serious.

But if you don't use that algorithm, then it's off limits.  It's 
considered broken.  It's not a sound design decision to use an algorithm 
with known weaknesses, just as it is not a sound design decision to use 
an algorithm that hasn't gone through a lot or review.  It has to go 
through this unscratched, that's the whole point of it.

IMHO, the whole approach of block ciphers is problematic.  You want a 
pseudo-random function that is bijective, i.e. it already violates one 
of the tests for randomness by design: It does not meet the birthday 
paradox, and it can not.  That by itself is 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.  That scares me, because if I can work my way 
backwards through the Keccak or Wurstkessel permutation/transformation, 
I know that all the other claims fall apart.  But that's because these 
functions have been deliberately designed for hashes, and that's under 
"known key" conditions, and then use this property to prove that all 
other modes of operations are secure, too.

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

[toc] | [prev] | [next] | [standalone]

#19544

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.

[toc] | [prev] | [next] | [standalone]

#19552

Paul Rubin wrote:

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

AFAIK, the attack does even work sometimes when your RNG is good.  
That's more worrysome...  I would have expected that the attack would 
work e.g. for one out of 2^240 keys or so (i.e. closely relateded keys), 
but it works for one out of 2^35 keys (somewhat related keys).  That's 
still not practicable, but a lot more than it should be.

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

Yes, and even protocols like SPDY, which could do a redesign, still use 
SSL/TLS.

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

It means that the relation between keys doesn't have to be strong.  A 
weak relation is sufficient to "break" the algorithm.

>> 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 feasible 
> distinguished
> from a random permutation.  It doesn't make claims about related keys.

I would expect from any cryptosystem that a related key results in a 
totally unrelated cipher stream.  E.g. a stream cipher has the property 
that you are allowed to use each key only *once*.  So a perfectly valid 
approach is to have a shared secret (e.g. established by a key 
exchange), and a number, which you increment for each use.  If you use 
AES in CNT mode as stream cipher, this would trigger that weakness, so 
you can't do that.  You can do it with many other stream ciphers, like 
Salsa20, or Keccak in stream cipher mode, or whatever, it doesn't break 
anything.  But with AES-256, it is considerably weaker.  AES-128 and 
AES-192 don't have this problem.

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

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.

> Really, the previous standard (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.  From today's 
point of view, DES was a complete no-go-area.  It turned out that the 
NSA did good work on the S-box (they hardened it for known attacks), but 
it could have been the reverse (implementing a backdoor).

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

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

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

The attack on Merkle-Dangard constructs succeed, because in each step 
you induce as many bits as there are in the internal state; this is a 
reall bummer.  Therefore, wide-pipe MD and sponge functions, which have 
a residual state.  In so far, we know what went wrong, and what to do 
against it.

>> but they only started it when MD5 was too weak to be used any longer,
> 
> Maybe you mean SHA1.

SHA-1 was weakened, and was though to break down soon, but the reason 
was that MD5 did really fail, with practical approaches to attack it.  
And the whole construct was known to be weak.

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

With the conservative 24 rounds, yes (said to meet its claims starting 
with ~12 rounds, the rest is just for "feel good" values; yes, it *does* 
feel better with more rounds).  It's about 11 cycles/byte on a Core i5, 
the "tuned" version should be good for <6 cycles/byte.  Salsa20 should 
be in the order of 3 cycles/byte (4.something on an Athlon-64).  But 
then, you need authentication.  Poly1305, which is Dan Bernstein's 
recommendation has another 2-3 cycles/byte (3 cycles on Athlon-64).

This both takes advantage of having secrets: The stream cipher starts 
with an unknown state, and the hash is keyed with a secret key.

If you use AES+SHA1 in software, you have about 40 cycles per byte.  If 
you use AES+GCM with AES-NI, you have AFAIK 4.5 cycles per byte.  If you 
would implement Keccak in hardware, one round per cycle (that's easy to 
do, much easier than AES, where you need 16 single-cycle s-box lookup 
tables), you would have 5 bytes per cycle.  Keccak was also chosen for 
being really fast in hardware, which makes it slightly slower in 
software (more rounds until it is sufficiently random).

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

You should read the Keccak paper.  They do have a mathematical 
definition, and their benchmark is "random oracle".  I.e. the 
transfer/permutation function must produce an unrelated output from any 
input (the total state of the sponge function), and if it does so, the 
hash will be secure.

The main thing that's different from the AES spec days is that now, we 
don't specify cryptography for "classified documents", i.e. some few 
off-site encrypted files, which may get uploaded to Wikileaks, we 
specify cryptography for everything, including ultra-high-speed local 
connections; thanks to the crazy media industry, even the signal to our 
monitors are encrypted ;-).  We have AES in hardware, because BluRay 
players wasted half their CPU time on decrypting the DRM content...

Same for SSL: When it was made, it was for "signing on" and "online 
banking".  Now, we do SSL on Facebook, for sharing pictures of cats and 
dinner plates.

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

[toc] | [prev] | [next] | [standalone]

#19602

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.

[toc] | [prev] | [next] | [standalone]

#19622

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/

[toc] | [prev] | [next] | [standalone]

#19567

On Tuesday, February 5, 2013 6:29:10 AM UTC-8, Alex McDonald wrote:
> On Feb 5, 11:01 am, Mark Wills <forthfr...@gmail.com> wrote:
> 
> > On Feb 5, 10:59 am, Mark Wills <forthfr...@gmail.com> wrote:
> 
> >
> 
> > >http://www.theregister.co.uk/2013/02/04/unlucky_13_crypto_attack/
> 
> >
> 
> > The method used seems quite tenous to me...
> 
> 
> 
> (Technically it's TLS they broke.) The problem has been known about
> 
> for over a decade. The advice is to use code that is slow to run; see
> 
> scrypt https://tools.ietf.org/html/draft-josefsson-scrypt-kdf-00 for a
> 
> standardised mechanism for this that is prohibitively slow to use for
> 
> the repeated attempts that all these cracks require.

Alex you the man today.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web