1
$\begingroup$

This question is on docimology (the science of teaching, learning, and passing exams), specifically applied to Multiple Choice Questions on cryptography. It's inspired by this question closed as homework without enough effort shown.

On a school's final exam (Applied Cryptography course per some online resource), it's asked:

On average, against a 128-bit-long key, how many more hash computations would an attacker need to perform to break weak collision resistance compared to breaking strong collision resistance?

In other words, if it requires $x$ number of hash computations to break strong collision resistance, how many computations would it require to break the weak collision resistance? $$A:2^{127}x\quad\quad B:2^{128}x\quad\quad C:2^{64}x\quad\quad D:1x\quad\quad E:2^{63}x\quad\quad F:2^{256}x$$

Stating that the question is wrong is not an option. How do we get to the answer that will be accepted?

$\endgroup$

1 Answer 1

1
$\begingroup$

When working on a problem, it helps to identify the words or expressions that it uses and seem central to the issue. Here, we have, in order that comes to my mind

  • "hash". Ah, I see what that is: a function that gets a bitstring in and outputs a bitstring out, typically of fixed size, and random-looking for one that do not know the inners of the hash. I remember of two properties of good hashes: it should be hard to find two inputs with the same output (a collision), and it should be hard to find an input with a given output (preimage); with two variants of that: only the output is given (the problem is finding a first preimage), or an input with that output is given (and the problem is finding a second preimage).
  • "weak collision resistance" and "strong collision resistance". Crap, I can't recall exactly what these mean, but my best bet is that must match resistance to finding collision and preimage, in some order.
  • "a 128-bit-long key". Hell, a key? There's no key to a hash. Let's assume that key is the result of the hash and move on (perhaps the question was truncated from the tale explaining that).
  • "how many (..) hash computations would an attacker need to perform". Ah, we are not counting computational or cryptanalytic effort, we are counting in number of hashes made in some brute force attack, and consider how many are needed as a minimum, not how many would be actually made.
  • "on average". Ah, we are considering average number for such attack, rather than e.g. maximum.
  • "on average...how many more...": it's asked the arithmetic mean of the difference. No wait, "In other words, if it requires x number of hash computations..." and the possible answers contradicts that, and tell in no uncertain terms that we are interested in the average ratio, or is it the ratio of the averages? OK that's not the same mathematically, but compared to the discrepancy between difference and ratio there is in this question, we can leave that detail aside.

How many hashes do we need on average to break preimage-resistance? There are $N=2^{128}$ possible 128-bit values. At each try, we have probability $1/N$ to succeed. The expected number of trials for success is $N$ (see this), that is $2^{128}$. Note: the conclusion that we would need on average $N/2$ hashes would be wrong: we are not enumerating a set of $N$ values in search for the right one.

How many hashes do we need on average to break collision-resistance? Well there is this thing called the birthday problem (or improperly, paradox), that a collision among values drawn uniformly among $N$ becomes likely somewhere near $\sqrt N$ (actually $1.177…\sqrt N$, see this), so the expected value is not far from that (it's within 0.3% of $\frac54\sqrt N$). So within <30%, it's needed on average $\sqrt{2^{128}}=2^{128/2}=2^{64}$ hashes.

So our ratio must be $2^{128}/2^{64}=2^{128-64}=2^{64}$ (and "weak collision resistance" must be preimage-resistance, since the statement implies it's the hardest). Let's tick C.

Let's leave aside until after the exam ranting about that:

  • we have no clue about "key";
  • we computed a ratio of average rather than average of ratio as any over-picky person would conclude from the question;
  • the average number of hashes before collision is >25% higher than we accounted, thus the true answer is correspondingly less than $2^{64}$, but the problem is worded as if an exact answer was among those proposed;
  • actual attackers really "need" to make sizably more hashes than the bare minimum leading to a collision, because they can't afford the memory and the cost of access necessary to store $2^{64}$ hashes and compare each to the previous others. So the true answer is further less than $2^{64}$, and it would not be surprising if the ratio got down to $2^{63}$ (answer E), or even less than $2^{62}$ with basic Floyd's cycle finding (in which case the correct answer would be D if we settle for the arithmetically closest answer, or still E on a log/geometric scale).

Takeaways

  • In evaluating something in cryptography, don't hesitate to make wild approximations: anything within 30% is go, compute the expected value of a function by evaluating it at the expected values of it's inputs, and so on.
  • If you hesitate between two options, go for the simplest even if wildly unrealistic (like adversaries with infinite and instant-access memory), unless the question explicitly tells otherwise.
  • When some of the vocabulary in the question is alien, bet that it matches the important notions that you know around the problem at hand (within reason if there is a penalty for wrong answers).
  • When part of the question seems to make no sense, and it's possible to ignore it, do.
  • If you must choose between indisputably wrong proposed answers with a numerical value, go for the closest (arithmetically or logarithmically according to if the proposals better fit a linear or geometric distribution), unless there is some "none of the above" option, or explicit indication that for some questions all the answers are wrong and there's a penalty for choosing any.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .