Schneier on Security

Peter • November 4, 2008 5:19 PM

@Stumbling novice

The security of cryptographic hashes are usually measured against three basic criteria:

i) pre-image resistance, given a specific digest how much effort does it take to find a message that will hash to that same digest

ii) collision resistance, can you find two different messages that hash to the same digest

iii) second pre-image resistance; given a specific message, can you find a second different message that produces the same hash value

For an n-bit digest from a secure hash you’d expect to have to do as much computational work as 2^n hash invocations to solve (i), 2^(n/2) to solve (ii) and 2^n to solve (iii). Notice that solving (iii) implies you can solve (ii).

Now, in a practical sense that doesn’t always mean the algorithm is weak – say for example you have a hash function which produces a digest of 512-bits in length, then you’d expect to have to do 2^256 work to find a collision. If you can find a collision in 2^250 work, say, then the algorithm is theoretically weak but that may have little practical relevance. Having said that, attacks on an algorithm are only going to get better so a theoretical attack may be an indicator for the future – which is why NIST has created the SHA-3 competition in the first place (there are serious questions over SHA-2 family).

Peter • November 7, 2008 9:34 PM

@CombatFighter:”If NIST allows you to make a minor fix, then they should allow minor fixes on many other submissions too, including broken ones!”

Personally, I’m hoping that minor fixes are allowed as my own algorithm was “broken” by an oversight which I didn’t pick up until after the deadline (was a very odd feeling publishing a collision for my own submission… anyway…).

Importantly, in this case, the security of Skein isn’t affected so one (namely NIST) could decide whether the reference implementaton or the specification is authoratative and base the evalutation on that (which in the end wouldn’t affect the analysis)

My own guess it that something as trivial as the error here isn’t going to be an issue, and in other cases the issue will likely be determined over a longer period of time with regards to the amount of public interest and type of fix required, i.e. a coding or small specification error may not be important, but a major design flaw could be.

The process, as far as I see it, gains a lot of benefit from public involvement and as such any public support/disapproval should be the principal determining factor in these situations – although others may and probably will disagree with me here.

If the NIST submission criteria were taken in a very strict sense, then (from my own insight) a lot of the submissions will probably fail or be border-line on qualifying as a “complete and proper” submission – so we’ve still to see if there’s a cull of algorithms when NIST publishes the candidates.

Peter • November 8, 2008 2:33 PM

@Clive Robinson, immediately above.

I think that Paeniteo, in this example at least, is correct in his assertion.

I may be wrong but the idea of iterating the hash function x number of times to increase the run-time is codified in PKCS #5 (PBKDF) and is even used in Bruce’s PasswordSafe software.

This obviously operates under some assumptions; off the top of my head you would at least require the hash function to be resistant to pre-image attacks, it should be bijective (or very close) and it should have no short cycles either on the whole digest or on a sub-set of those bits. Which conveniently enough are all properties without which the hash function is weak in almost every other scenario as well.

The example you used of a one-time pad, I would suggest, isn’t used correctly. I would argue that increasing the iterations” here would be analagous to using more than a single pad – which wouldn’t necessarily increase the security but would certainly not weaken it. Again, with your example of addititive and multiplicative operators – this can be extended to exponentiation in a finite field giving the well known problem of discrete logarithms, or for that matter the factoring of two large primes…. both of which under the correct conditions are secure constructs.

Your point that there may not be a simple relationship between chaining and required workload I would certainly take as valid, but personally I think the main dangers are from the inappropriate use of primitives rather than the iteration of a secure primitive.

Peter • November 13, 2008 9:58 AM

@greg:’ However in this context of a “hash function is too fast” I think I still have a point. like with a hash cash type approach.’

I think you’re missing the point here Greg; you can make a fast hash function arbitrarily slow (your construction would be an example), you cannot make a slow hash function faster. So as long as the hash function itself obeys certain security criteria, the fast hash function is better as it covers both scenarios.

‘Of course this is still not secure really. It just makes kiddie hackers slower…Preventing off line attacks is where the effort should be done’

The iterative idea is to do just that – make off-line attacks more difficult. If hashing a message m takes t time then doing a PBKDF style construction, then with i iterations it will take i times as much computing power for anyone – script kiddie or not.

Any basic timing issue would be down to the fact that the computational effort only grows linearly with the number of iterations – so 1,000 times more work on a desktop might be bad, but on a grid computer it may be proportionally smaller.

Peter • November 13, 2008 4:20 PM

@Clive Robinson:”Now the real question is can it be done in a way where there is an exponential not linear rise in effort with the number of iterations so that we can get off Mr Moore’s et al, downwards security slopes for a while”

Personally, I would doubt it. I should probably expand my last post because I seem to have missed the crux of the problem.

Normally to verify a password the host will take the supplied user’s password, hash it with a salt and compare the resulting digest with its recorded digest. If an attacker wants to brute force, he/she can begin by trying the password candidates in turn with the most likely first. Now assume that the attacker has to try k passwords (where k is assumed to be reasonable as compared to normal password complexities), and that the time taken (or more appropriately the work required) to compute a single hash result is l. Then for a host to verify a password it takes l time, whereas an attacker will expect to expend k.l.(1/2) time (or work – especially since the attacker will likely highly parallelise the computation).

In the PBKDF the initial password and salt are hashed i times, so the host has to do i.l work, while an attacker can expect to need i.k.l.(1/2) work.

Hence the linear growth. The problem arises because the host’s effort in verifying a password also grows linearly, but a few seconds for a host to verify a password (usually) isn’t a problem – whereas in an attack scenario that i factor may make an attack infeasible.

You could in theory create a construction (I think) where the computatal work required is exponential in i, but that would also mean the work required to verify the password on the host is also exponential in i – making it unworkable.

As far as I can tell the only way to improve this scheme without modification is to improve password complexity, hence increasing k which only affects an attacker.

As long as the hash function is pre-image resistant (and probably collision resistant, if we need to be strict about the argument), and that the block size contains more entropy than the assumed password set – then it also doesn’t matter what hash function is being used (we can just change i to adapt). A result which is not necessarily intuitive.

There are other authentication methods availble which either move the password problem to the client (and thus negating the avanue of an attacker gaining another user’s password), or remove the necessity for a password completely. Public key authentication (moving the password problem to the client – i.e. the password used to protect the private key) and certain token authentication (one-time password schemes) come to mind.

If you’re serious about authentication security, I’d strongly suggest either a public key, or a decent token or cryptocard solution.

Peter • November 28, 2008 7:43 AM

@Nicholas Parimore:Why try and design something slow when you can take something fast and iterate it ‘n’ number of times to make it as slow as you like? The PBKDF stuff I was talking about further up the list does what you’re asking – its really only parallelisable in the number of attempts at one single time, which is pretty much algorithm independent anyway.

@PackagedBlue:There is a way to do this, I’d mentioned it further up the list… PBKDF (c.f. PKCS #5).

Peter • December 25, 2008 8:28 PM

@Nicholas Parimore:”An algorithm that establishes a baseline speed that can’t be significantly sped up provides extra assurance. That’s unlike some modern MMX- or SSE-enhanced algorithms, or Skein’s hash-tree mode.”

I think the point has been missed. There are very few applications where a hash algorithm being slow is actually preferred – PBKDFs are one of them. In that scenario, the attacker has to use the same hash in exactly the same manner as the implementation – which is unlikely to be a hash-tree. We can also tacitly assume that MMX or SSE gains have already been factored into the implementation’s iteration count.

So in effect, the speed-ups you talk about are already accounted for. If brute-forcing, then the only way to really improve speed is to parallelise it (or create a massivly parallel hardware implementation) which means the benefits of any purpose built algorithm are essentially redundant.