The Side Channel

forest

04:00

Fun fact: There's still a use for MD4 on millions of devices. The popular ext4 filesystem in Linux uses half-MD4 internally to generate a hash tree. I'm sure there are plenty of other uses too, even for MD5. — forest 2 mins ago

I wonder how many other places it gets used.

Ilmari Karonen

10:35

I might be biased here, but I'd kind of like to see crypto.stackexchange.com/questions/32247/… reopened. Mostly because I spent some effort on writing a half-decent answer to it, and that answer would not really be suitable for the question it was closed as a duplicate of. Opinions?

forest

11:08

@IlmariKaronen I cast a reopen vote on it.

If your answer answers the question but wouldn't answer the duplicate, that's strong evidence that it should not have been closed as a duplicate.

Ilmari Karonen

Thanks. :)

SEJPM

13:11

@IlmariKaronen I think the standard ruling for duplicates is "if the answers to the 'original' fit the 'new' question, then then 'new' question is a duplicate"

in this case I can see the difference in the request for a simple explanation with numerical examples

which you provided but isn't a given in the other Q&A

so TL;DR: I reopened

Squeamish Ossifrage

13:36

It's funny how controversial it seems to be among a certain crowd here to identify a common conceptual structure—encryption with c = m + p when p is used only once—that fits neatly into a clear conceptual framework widely used in the literature of a theorem for information-theoretic security of the idealization that naturally leads to theorems for computational security of approximations.

I wonder: would the reception among that crowd be better or worse if I called it ‘XOR encryption’? (That doesn't even emphasize the one-time part!)

-3

A: What are some real world examples where one time pad encryption is used or can be used?

When you browse to https://crypto.stackexchange.com/ or https://bankoffreedonia.com/, your browser almost certainly uses a one-time pad generated by AES-256 or ChaCha or similar to encrypt the messages exchanged with the server. We call this method of generating a one-time pad a ‘stream cipher’....

-2

A: Does ChaCha20 counter actually increment through iterations?

The nonce is a parameter to the message cipher, along with the key and the plaintext of a message. It distinguishes messages. For example, it might be the number of complete messages that have been sent so far. The counter is internal state in the message cipher which increments for each 512-b...

Curiously, a discussion of that conceptual framework appears to be unobjectionable:

2

A: What is the difference between information-theoretic and perfect types of security?

For a type of cryptosystem with a security goal, like a 128-bit authentication tag on a message aiming to prevent forgery, perfect security is the best security we could possibly hope for with any cryptosystem of that type. For a model or family of cryptosystems of a particular type aiming for s...

Ilmari Karonen

13:52

@SqueamishOssifrage "XOR encryption" might not be the best choice, since it's quite commonly used for insecure schemes with a repeating keystream (i.e. basically Vigenère over $\mathbb Z_2$).

(Other than that, I don't really feel like commenting without first understanding the context, of which there seems to be quite a bit.)

Squeamish Ossifrage

@IlmariKaronen Right—it seems obvious that ‘XOR encryption’ is worse precisely because it doesn't carry the implication that the pad must not repeat.

@IlmariKaronen Not sure there is much more particular context! Broadly, I see a phenomenon that many people are regularly misled by presentation of the term ‘one-time pad’ as an exalted ideal of perfect security into discarding everything else about modern cryptography under the misapprehension that it is bad—and invariably generating their pad by some hare-brained scheme that shoots themselves in the foot, when the model of c = m + p for one-time p is ubiquitous in modern cryptography.

Maybe if we point out that it's an extremely mundane design principle that's used ubiquitously in modern cryptography, it will lose its sexy appeal.

How do we ensure that m + ChaCha(k, n) is secure? It follows directly from the requirements of the model: 1. The pad p in c = m + p has to be close to uniform random for the information-theoretic security theorem, so ChaCha(k, n) had better be hard to distinguish from uniform random. 2. The pad in c = m + p must not be repeated, so we can't use the same (k, n) twice to generate ChaCha(k, n). Just an instance of the very mundane one-time pad model, taking advantage of the usual theorem.

Ilmari Karonen

14:20

@SqueamishOssifrage To my ear at least, the term "one time pad" does carry connotations of both historical usage (I mean, it literally refers to printed paper pads) and unconditional security (because that's the context in which it's typically used; although I just checked, and it looks like Shannon didn't use the term, so I don't really know where it originally comes from). If I didn't want those connotations, I would not use that term, at least not without qualifying it.

Anyway, the distinction between "stream cipher" and "one time pad" feels kind of like the distinction between "pseudorandom" and "random". Sure, you and I know that the former can be practically just as good as the latter (and the cranks don't, and think the latter is magical), but it's still useful to be precise and make the distinction.

Squeamish Ossifrage

If a historical pad were generated by a machine, or didn't have perfectly uniform distribution, would it be excluded from the term ‘one-time pad’?

In the absence of specific historical evidence of perfect uniformity of the process used to generate the pads, I think that rule would exclude every actual use of the one-time pad model in history. But nobody objects to using the term for historical cryptography.

In practice, what we often call ‘one-time pads’ in historical cryptography obviously weren't—otherwise, e.g., the VENONA project would never have been able to break any of it!

I agree that it's important in very specific technical contexts—of stating and proving particular theorems—to distinguish between a random variable with some distribution, and a deterministic function with some presumed bounds on advantages. But outside that context, what's the use of the term ‘one-time pad’ except to get people excited about shooting themselves in the foot?

One answer is: nothing, use of the term is forbidden except in idealized sexy magic. Another is: it's a ubiquitous and mundane design principle and it's not actually very interesting on its own.

Ilmari Karonen

@SqueamishOssifrage Arguably no, at least not if one was quoting a historical source that used the term. And I do have sympathy for your attempt to redefine it to get rid of those "magic" connotations, but I fear you're both swimming against the current and introducing terminological confusion by doing so.

3

@SqueamishOssifrage Basically, to me, the appearance of the term "one time pad", especially when unqualified, means that the author is either a) discussing historical cryptosystems, b) using it correctly as a term of art in a very specialized niche corner of modern crypto theory, or c) a crank.

Squeamish Ossifrage

What I find funny is that this is taken as a redefinition rather than just an instance of a model! There's a clear conceptual connection between c = m + p, where p is close to uniform random and never repeated, and c = m + p, where p = ChaCha(k, n) where k is uniform random and n is never repeated and thanks to ChaCha p is hard to distinguish from uniform random. Terminological confusion arises when the terminology suggests these are unconnected.

Ilmari Karonen

[...] And I know you're not a crank, which is why it's so jarring to see you toss it around in that answer you linked to earlier, especially without any explanation. Because if that answer was written by some random user I didn't recognize, my first impression would indeed be that they're confused about modern crypto terminology and probably indeed one of those people who think OTP = "magic security that makes everything perfect".

All just because of that one out-of-place phrase.

Squeamish Ossifrage

14:37

It seems to me that saying ‘m + ChaCha(k, n) is not a one-time pad’ is fodder for cranks to invent a hare-brained substitute for ChaCha(k, n) to make a ‘real one-time pad’, while saying ‘m + ChaCha(k, n) is a[n instance of the] one-time pad [model]’ emphasizes that the difference between the crank's invention and ChaCha is not the ‘one-time pad’ part but the hare-brained scheme vs. ChaCha.

Ilmari Karonen

I can understand your viewpoint. But I feel that, in current usage, the term "one-time pad" is so strongly associated (one might perhaps say "tainted") with connotations of "true randomness" (as opposed to pseudorandomness) that if you want to use it in a broader sense (and if you do, more power to you!), you kind of need to explicitly say so.

Squeamish Ossifrage

Obviously the audience for this emphasis is not severe cranks—who will think whatever they want—but for inexpert onlookers who have a harder time telling experts from cranks. If I point out that the crank has just used a ubiquitous, mundane design principle—the one-time pad—but combined it with a lot of nonsense for the pad instead of a design that has had decades of scrutiny, that likely makes the crank's emphasis on the amazingness of the one-time pad maybe a little less amazing.

Ilmari Karonen

Mmm, sure. But remember that it kind of goes both ways. By using the term "one time pad" in the context of legitimate modern stream ciphers, you're also legitimizing that term in that context. Imagine one of those "inexpert onlookers" reading your answer and going "oh, so if I want secure encryption, I need a one time pad... let me just google that up!"

Squeamish Ossifrage

Also makes for a simpler definition: the one-time pad model is just encrypting a message m by c = m + p for a single-use pad p close to uniform random. No need for case-by-case breakdown of (a) historical ciphers, (b) technical cryptography theorems, (c) cranks.

@IlmariKaronen The point that I emphasize is that everything interesting is in the selection of pad; the application of the model is then a boring step to combine the pad with a message.

Sure, the crank is using the one-time pad model—no big deal, lots of people use it, but the security depends on how the crank generates the pad, which (a) hasn't gotten decades of scrutiny and (b) turns out to be a load of predictable and biased nonsense.

Ilmari Karonen

14:52

... And, you know, I just read your answer again and noticed that it does include a pretty long "crank warning" at the end. But still, something about the way it's written feels off to me, as if (without the surrounding context) I'd need to read it several times just to be sure that it's a valid answer with a warning about cranks misusing terminology, rather than a crank answer with a warning about everyone else misusing terminology. :/

Squeamish Ossifrage

‘I generated a one-time pad from /dev/random!’ Well, yes, you're using a one-time pad, but if you look at what /dev/random is under the hood, you've just used ChaCha or AES-CTR_DRBG or whatever to generate the pad.

@IlmariKaronen Which one?

Ilmari Karonen

I meant this one: crypto.stackexchange.com/questions/67519/…

Squeamish Ossifrage

I certainly acknowledge that there is a kind of sociological barrier to using the term one-time pad this way. But I don't think that sociological barrier serves anyone except cranks!

Ilmari Karonen

Well, it kind of also serves people trying to tell cranks from sane people with a decent understanding of cryptography.

Anyway, regarding that particular answer, I feel like just amending the first instance of "a one-time pad" in the first paragraph to, say, "a pseudorandom one-time pad" might go a long way towards making it clear at first sight that you're not using the term "one-time pad" in the cranky (and/or the narrow information-theoretic) sense there.

Squeamish Ossifrage

15:08

Well…but pseudorandom is a property of a deterministic function family, and in this case, the pad actually is a random variable!

Specifically, k is a random variable, and ChaCha(k, n) is also a random variable, and the fact that it works as a one-time pad is a consequence of the pseudorandomness of ChaCha.

What's really important is statistical distance of the pad from uniform random as detectable by any distinguisher: make it small enough not to matter. (Could flip coins—but that gives a slightly nonuniform distribution too!)

Ilmari Karonen

@SqueamishOssifrage ...from the attacker's viewpoint, and assuming that you're using the Bayesian definition of probability (or imagining an infinite sequence of independent trial attacks for a frequentist interpretation, I suppose). But from the communicating parties' viewpoint, the key is a known constant and the keystream is deterministically generated from it.

Squeamish Ossifrage

Sure, but the process of having the conversation entails drawing a key at random. Once you have a pad p, the computation of m + p is deterministic too, but the process of choosing p at random and then using that to compute m + p is the object whose security can be studied.

Ilmari Karonen

But anyway, that is kind of splitting hairs. Maybe "pseudorandom" isn't the word you'd like to use, but I feel there ought to be something there to make it clear that you're not assuming "one-time pad => each bit is truly uniformly and independently random" there.

Also, in particular, the user who asked the question does seem to be assuming that. (They start their question with "I understood that One-Time Pad (OTP) encryption ensures perfect secrecy.") So I feel like your answer is a kind of a "frame challenge" in SE jargon, and probably should present itself more clearly as such, lest it be mistaken for "not answering the question as asked".

Squeamish Ossifrage

15:32

That's reasonable. I'll rearrange it a little to address the ‘perfect secrecy’ question earlier.

Ella Rose

16:10

> My religion does not recognize any other hashing algorithm than MD5

XD

"My religion does not recognize any other hashing algorithm than MD5"... That's my kind of religion! Where do I sign up for the crusade against those smug SHA-2 heretics? — ANone yesterday

...

> I hire someone, who lives in a closet under the stairs in the Ecuadorian embassy with nothing but his cat and his colossal narcissism to entertain himself

This is easily the funniest Q/A on crypto.se in as long as I can recall

Crypto HNQ

18:50

1

Q: Is it possible to determine the symmetric encryption method used by output size?

I'm attempting to identify the method of encryption for a black-box symmetric encryptor that produces blocks of output that are 4 bytes in length (e.g. small inputs fit in 16 bytes, then 20 bytes and 24 bytes as more input characters are added). It's symmetric encryption and the value is always ...

Transcript for