Miscellaneous feedback on first few sections

[lgarron]

(Note: I've been divvying up this ticket into many smaller tickets and editing this description as I go along. --lvh)

• Page 35

Knowing a bunch of (input, output) pairs shouldn’t give you any information about any other (input, output) pairs[footnote 1].

Even with the footnote, this is a bit disingenious. Of course, the "right" way to say it that any number of (input, output) pairs don't give you information about other pairs than you would know about a random function conditioned on the given pairs.

I would also put in an explicit emphasis that many security proofs rely on the fact that you use a random key (out of all possible keys) for this assumption to hold.

• Page 36 (Section 5.2)

That’s okay: that tiny fraction is still more than large enough that it’s impossible for an attacker to just try them all.

Sorry to be blunt, but this is completely beside the point. What matters in this case is that any (random) permutation from the small fraction looks just as random as (a random) one from all permutation.

It is, of course, trivial to think of examples where the attacker can't try them all -- yet the cipher is completely insecure. (And it's even possible to do this while keeping it fairly random-looking on first inspection.)

[lvh]

Thanks for your comments. Would you mind submitting separate issues? That would make it much easier to make sure none of them are neglected.

One I can address now:

• Page 14, Intro:

  "By seeing how many systems that are ostensibly secure to the layman, you will understand why certain primitives and constructions are necessary." Word missing?

This is fixed in master. I've edited the ticket description and removed it.

[lvh]

I've also made an issue for you already for the permutation diagram thing in #83.

[lvh]

It's called a one-time pad because it involves a sequence (the "pad") of random bits. In order to providing a clear distinction between "pad" and "padding", perhaps give the etymology?

I don't know about the etymology. Can you be more specific?

• Page 25

  Unfortunately, most commercial “one-time pads” are snake oil, and don’t satisfy at least one of those two properties. I would first add a sentence stating how various products will try to claim that they're using one-time pads. I also wouldn't use "snake oil" without explanation(/footnote/glossary). It appears to the be the only use of the phrase in the book right now. The section should probably make it explicit that it is talking about fake one-time pads that therefore aren't actually one-time pads. In my opinion, scare quotes don't quite get that across.

I've addressed this in master, removed from the ticket description.

Page 39 (Section 5.3)

If 3DES had been defined as E(k1, E(k2, E(k3, p))), it would’ve been impossible to use 3DES implementations for systems that required compatibility with DES. Well, sure. But then you would just expose the single-encryption version as a separate API. I think what you want to state here is that the definition that was adopted conveniently does allow reusing the 3DES API for DES encryptions -- which may be useful if you're trying to do this in hardware, want to keep your software API minimal (but still allow DES if needed).

Yes, hardware was precisely what I had in mind here; it's my understanding that that was also by far the biggest motivator. I'm not sure the word "implementation" vs "API" changes anything: the point is that you take a 3DES black box and you can have the effect of a regular DES encryption/decryption, right?

[lvh]

Page 35

Knowing a bunch of (input, output) pairs shouldn’t give you any information about any other (input, output) pairs[footnote 1]. Even with the footnote, this is a bit disingenious. Of course, the "right" way to say it that any number of (input, output) pairs don't give you information about other pairs than you would know about a random function conditioned on the given pairs.

I'm having difficulty parsing this sentence.

I would also put in an explicit emphasis that many security proofs rely on the fact that you use a random key (out of all possible keys) for this assumption to hold.

That's a good point; I definitely need to hammer that cryptographic keys are cryptographically random, not only here, but elsewhere in the book.

[lvh]

A block cipher is a keyed permutation. In the set of possible blocks, which is the set of all possible byte sequences of the cipher’s block size, the block cipher maps every block to some other block. To me, emphasizing something as a keyed permutation would imply that you've already gone over permutations. The next sentence is also a bit awkward. I'd change "some other block" to "a different block", but I don't have a great suggestion for restructuring the start of the paragraph.

Actually, it's emphasized precisely because I haven't gone over it already ;) I reworked the paragraph to make it clearer what that means.

[lvh]

Page 24 [diagram] The output c_i is fed back immediately, and c_i/the notion of ciphertext has barely been introduced. I think it would be better to separate encryption and decryption, either by putting them on separate lines or by drwing something in the middle.

Are you referring to this diagram?

That's on page 27, but that's also the only diagram I can see this comment making sense for; maybe you're looking at PDF reader pages and I'm looking at page numbers on the pages themselves?

Anyway, assuming it is about this one; I'll add the c_i/p_i references in the surrounding paragraphs; I think that together with the following diagram where Eve is eavesdropping that is pretty clear.

[lvh]

Page 27 [example images] Nice example! However, I would probably rearrange things. I understand the motivation to put the plaintext and ciphertext in the current layout, but putting the key at the end looks weird. What about switching (b) and (c)?

Thanks :) I'm assuming you're referring to this:

Swapping (b) and (c) might look better (I don't really care either way), but that doesn't affect where the key ends up, which IIUC was your main complaint. Did you mean two other images?

[lvh]

Page 36 (Section 5.2) That’s okay: that tiny fraction is still more than large enough that it’s impossible for an attacker to just try them all. Sorry to be blunt, but this is completely beside the point. What matters in this case is that any (random) permutation from the small fraction looks just as random as (a random) one from all permutation.

It is not sufficient and I agree the text can be interpreted as saying it is, but it's hardly "completely beside the point"; it's certainly a necessary condition.

It is, of course, trivial to think of examples where the attacker can't try them all -- yet the cipher is completely insecure. (And it's even possible to do this while keeping it fairly random-looking on first inspection.)

Yes. I'm quite aware.

[lgarron]

Thanks for splitting some of this up into separate issues for me! I'll make sure to crate new issues if I have more comments.

Knowing a bunch of (input, output) pairs shouldn’t give you any information about any other (input, output) pairs[footnote 1]. Even with the footnote, this is a bit disingenious. Of course, the "right" way to say it that any number of (input, output) pairs don't give you information about other pairs than you would know about a random function conditioned on the given pairs.

I'm having difficulty parsing this sentence.

Sorry, I should have said "permutation" instead of "function" (PRP, not PRF...).

The sentence is okay, but the footnote makes this confusing: you should never reach "the extremes" for a real-world PRP. In any case, I would personally at advantage instead of saying "shouldn't give you any information".

Swapping (b) and (c) might look better (I don't really care either way), but that doesn't affect where the key ends up, which IIUC was your main complaint. Did you mean two other images?

No, I meant those. I think the resulting left-right structure is more intuitive, but I don't have a good reason for that.

I don't know about the etymology. Can you be more specific?

As far as I understand, it comes from physical pads with one-time information. Wikipedia corroborates this.

Yes, hardware was precisely what I had in mind here; it's my understanding that that was also by far the biggest motivator. I'm not sure the word "implementation" vs "API" changes anything: the point is that you take a 3DES black box and you can have the effect of a regular DES encryption/decryption, right?

I don't recall how much hardware was a motivation for 3DES. I was imagining that a software implementation of 3DES would presumably include a plain DES implementation, which would usually be be easy to expose in addtion to 3DES. I think mentioning hardware here would be useful.

That’s okay: that tiny fraction is still more than large enough that it’s impossible for an attacker to just try them all.

Sorry to be blunt, but this is completely beside the point. What matters in this case is that any (random) permutation from the small fraction looks just as random as (a random) one from all permutation.

It is not sufficient and I agree the text can be interpreted as saying it is, but it's hardly "completely beside the point"; it's certainly a necessary condition.

Hmm, after re-reading this a bit, it does seem more relevant in context (although the repeated word "possible" in the previous sentence is confusing.)

But among between "easy to brute-force all" and "easy to distinguish from random", the latter is stronger than the former -- and arguably implies it. There are many ways that a block cipher could be weak, and being able to enumerate all keys easily is just one (obvious) way it could fall. But the subset of permutations that the keys generate could have a lot more flaws.

[lvh]

Hi :) Thanks again for your comments. I've made the two changes in reffed commits, and I think the remaining changes will be handled by outstanding tickets re: formal definitions for semantic security as well as entropy and security levels. So, I'm closing this :)

If there are any other issues (or issues that were on this ticket but you felt were unaddressed or underaddressed), please don't hesitate to open a new ticket. While normally I encourage people to re-open tickets, this issue had the problem that it combined too many different things :)