The Side Channel

2:53 AM

1

Q: Formula for bits of entropy per bit, when combining bits with XOR

Assume that bits $A$ and $B$ each have .5 bits of entropy per bit. The two-bit result of the concatenation $A‖B$ has 1 bit of entropy total, and it retains the entropy density of .5 bits of entropy per bit. How many bits of entropy would the single-bit result of the exclusive-OR of $A$ and $B$, n...

b degnan

2:06 PM

@SqueamishOssifrage I have a question regarding you use of "trivial". I agree with the above statement regarding AES-GCM and the probability to find text valid under both keys. It seems like it'd be a huge key space to find that.

Squeamish Ossifrage

@bdegnan This is why it is counterintuitive and why reputable crypto.se users should not be cavalierly piling on falsehoods about an AES-GCM ciphertext's apparent commitment to a key! The key space is irrelevant. It's a tiny bit of linear algebra to construct such a ciphertext, for any two keys.

b degnan

Mathematically, it is trivial. I just don't have a feel for the pragmatic aspects as far as an attack.

It's like just brute forcing an AES key, no?

Squeamish Ossifrage

no

It has nothing to do with AES; it treats AES as a black box and uses it exactly as many times as two normal AES-GCM encryption calls would use it.

The linear algebra is in GF(2^128), the space of GHASH authenticators.

b degnan

yeah, huge. I looked at the "furry blog", and I didn't take away the complexities of actually calculating the shared result. I'll look later when I get some time. It's nice ot have you back btw. I learn things as you are more likely to share your immediate anxieties when compared to most people.

...well, back for visits

Squeamish Ossifrage

The size of GF(2^128) is not relevant: what's relevant is that you just have to solve a simple underdetermined linear system in it.

Fix two keys k, k' and even two nonces n and n' Let h = AES_k(0) and h = AES_k'(0)—these are the GHASH keys. The goal is to find two ciphertexts c = (c1,c2,…,cm) and c' = (c'1,c'2,…,c'm) such that GHASH_h(c) + AES_k(n) = GHASH_h'(c') + AES_k'(n'), meaning h^m c1 + h^{m-1} c2 + … + h cm + AES_k(n) = h^m c'1 + h^{m-1} c'2 + … + h cm + AES_k'(n').

b degnan

2:26 PM

gotcha, gotcha

thanks, that was super helpful.

Squeamish Ossifrage

That is, h^m (c1 - c'1) + h^{m-1} (c2 - c'2) + … + h (cm - c'm) + AES_k(n) - AES_k'(n') = 0.

But it gets better/worse (for adversary/defender). AES-CTR derives the ciphertext c_i from the plaintext c_i and the keystream u_i = AES_k(some function of n and i) by adding them in GF(2^128).

So it's very easy to control everything here. This is one equation in umpteen different unknowns; you can just pick almost all of the plaintext arbitrarily, and then solve for the one ciphertext block which will become garbage in your plaintext, but in many formats—such as images or PDF documents—there's plenty of room for a single garbage block.

Squeamish Ossifrage

2:47 PM

@bdegnan (I'm not really ‘back’—that is still held up on SE.inc's governance issues—just serving time in the peanut gallery since I saw some issues with some recent answers.)

b degnan

@SqueamishOssifrage still, I appreciate the time that you spend with the peanut gallery.

I'm looking forward to your future evisceration of answers. particularly mine.

Squeamish Ossifrage

3:11 PM

Well, I hope I don't eviscerate too much; I don't want to discourage people from contributing. But I do use strong language for people whose words carry great weight here.

… Of course, this reduction breaks down if the attacker may somehow choose $K_0$ as a function of (some information about) $K_1$ (that is not made available to the attacker in the course of a standard unforgeability challenge), even if they might not straight up learn $K_1$ itself, or, conversely, if the challenger may decide to cooperate with the attacker and choose $K_1$ after the fact based on $K_0$ (or on any other values chosen by the attacker). Hence my extra requirement that the two keys be chosen independently of each other. — Ilmari Karonen 57 mins ago

Ilmari is still under the misapprehension that independence is relevant. This attack works for any K_0 and K_1, unconditionally.

kelalaka

5:24 PM

@SqueamishOssifrage what is $n$ in GHASH_h(c) + AES_k(n) = GHASH_h'(c') + AES_k'(n')

I guess n is the number of 128-bit blocks in c

@SqueamishOssifrage the Asymptote code B is not working in my machine. crypto.stackexchange.com/a/70526/18298

surfacepen=material has problematic.

Needs something like surfacepen=material( diffusepen=gray(0.5), emissivepen=gray(0.6), specularpen=black));

Also, can I use it?

Squeamish Ossifrage

@kelalaka It's some encoding of the nonce/IV and the ciphertext length.

kelalaka

So it can be n+1

Squeamish Ossifrage

5:46 PM

nvlpubs.nist.gov/nistpubs/Legacy/SP/…

It's J_0 in the notation of that spec.

Squeamish Ossifrage

6:14 PM

@kelalaka Apparently Asymptote just summarily removed the ambientpen option. Try taking it out.

@kelalaka As with everything on SE, license is CC-BY-SA 3.0 or 4.0: you can use it with attribution under the same license to everyone else.

kelalaka

Thanks.

kelalaka

6:57 PM

@SqueamishOssifrage in this case it is all black sphere.
draw(unitsphere, surfacepen=white+opacity(.3));
This is nearest I can get.

Maarten Bodewes

7:30 PM

@SqueamishOssifrage Hey Squamish, welcome back (to the side channel anyway) :)

Was in a Applied Post Quantum Crypto Workshop from NIST this evening. Interesting stuff about migrating to a PQC world (or QSC world in ETSI wordings, can't see that one catching on). Tanja and Daniel also had a short presentation.

A bit too much talk about "Cryptographic Agility". Somebody thought that adding PQC would be a "drop in replacement". I'm sceptical, but I haven't implemented any PQC yet, so I might be wrong. With hybrid cryptography (both classical / old algos + PQC) I think that this agility is out of the Window, at the protocol implementation level anyway.

I need a low level ARM chip with Keccak already. Who's selling that?

b degnan

7:55 PM

probably could target an FPGA with Keccak pretty easily as it's little endian

Maarten Bodewes

@bdegnan Does it matter that much if it is little endian? I've programmed Skein without too much problems in Java and that's big endian (all the SHA-3 algorithms were required to be little endian after all).

But then again, I'm not a FPGA architect / dev :)

@bdegnan Not directly in the market. But I'm also moving in the direction of IoT, and I am playing with the idea to indicate that PQC should be considered for a particular client.

And a lot of algorithms seem to depend or at least use Keccak / SHA-3 in some form or other.

Note that hash based algorithms are in the final process of being standardized....

Seems that a direct DH replacement is indeed not in the planning by the way. KEM with ephemeral keys is going to take that place.

b degnan

8:23 PM

ARM is internally little endian, so it makes hardware integration easy because Keccak is little endian. You can literally drop the core without any work.

If you have any stream, it's nice if the endiness is the same because of DMA

Crypto HNQ

8:36 PM

1

Q: Cryptographic properties of field multiplication

While reading about AES-GCM, I discovered there is a multiplication over $\operatorname{GF}(2^{128}$). My question is about its cryptographic properties, such as: Take a random element $X$ from $\operatorname{GF}(2^{128}$) (which is not $0$ or $1$). Multiply it with a constant $Y$ (say, the plai...

finite-field

Maarten Bodewes

@bdegnan Oh, OK. But the little endian part is just on relatively small number values, probably mostly 64 bit (although Keccak has a few "strange" sizes internally, but I'd have to look at an optimized implementation to be sure). ARM is of course able to switch between LE and BE, but as it is generally run in LE mode I guess that makes relatively little difference.

or big difference :P

kelalaka

9:45 PM

Who proved HMAC-SHA256 is a PRP?

Maarten Bodewes

Uh, nobody?

Where does it say that?

kelalaka

10:03 PM

at he end of @SqueamishOssifrage answer if I understood correctly.

4

A: What is the difference between pseudorandom permutation/pseudorandom function/block cipher?

All three are families of functions. For example, $f_k(x) = k \oplus x$, where $\oplus$ is xor and $k$ and $x$ are 256-bit strings, is a family of functions; for any 256-bit string $k$, there is a function $f_k$ which given another 256-bit string $x$ returns the xor of $k$ and $x$. The input an...

Maarten Bodewes

I think that the hard to distinguish here is not identical to is a.

Similar to how a PRP is almost but not quite a PRF. Obviously for HMAC the inverse would be missing in action and yeah, although you won't find a collision, they would be present for inputs that are identical in size.

Squeamish Ossifrage

@kelalaka Works for me just removing the ambientpen argument to material (asymptote 2.62 from Ubuntu 20.04; was likely previously using asymptote 2.41).

kelalaka

mine is 2.51

could you paste that line?

Squeamish Ossifrage

If you mean the sentence
> Pseudorandomness is a kind of logic quantifier: for uniform random k, fk is hard to distinguish from a uniform random permutation, and it applies to specific function families like HMAC-SHA256.
it might have been more prudent to use AES-256 as an example.

kelalaka

yes, exactly.

Squeamish Ossifrage

10:15 PM

That said, you can still ask the question: Is HMAC-SHA256 a PRP? Certainly it's extremely unlikely to be a permutation, but because of the collision resistance, you actually have no hope of telling whether a black box you're given is (a) a uniform random permutation or (b) HMAC-SHA256 under a secret key, restricted to 256-bit inputs.

kelalaka

And the input is restricted, then?

Squeamish Ossifrage

?

kelalaka

The inputs size of HMAC is not restricted to 256-bit, so to play the game we should setup up a restriction, too?

Squeamish Ossifrage

Yes, HMAC-SHA256 restricted to 256-bit inputs makes a reasonable PRP because you have no hope of distinguishing it from a uniform random permutation if you're merely given a black box that has one or the other.

(It doesn't make sense to ask whether HMAC-SHA256 on input sizes other than 256 bits is a PRP.)

Maarten Bodewes

I think that using AES-256 would definitely require less discussion :P

kelalaka

10:21 PM

So being prolix good to all at some point :)

Squeamish Ossifrage

(It does not, however, make a strong PRP because you can't compute the inverse; a PRP adversary merely has access to the forward direction, while a strong-PRP adversary has access to the forward and reverse directions.)

Squeamish Ossifrage

11:18 PM

0

Q: Is any encryption system that changes keys for each session "forward secure"?

As far as i understand, a encryption system is forward secure if new session keys are generated for each session, which is also part of what wikipedia says about forward secrecy: By generating a unique session key for every session a user initiates, the compromise of a single session key will no...

encryption public-key forward-secrecy

is a duplicate of

0

Q: What is the difference between forward secrecy and key freshness?

Is all random private key that generating a unique session key is both forward secrecy and key freshness?

public-key key-exchange forward-secrecy

although there's a somewhat better answer at

6

Q: Is encrypted e-mail sent over TLS 1.3 a form of "forward secrecy" (similar to something like Signal)?

One common complaint about GPG-encrypted e-mail is that it doesn't provide forward secrecy; however with opportunistic TLS becoming increasingly common in both IMAP and SMTP, it's not unreasonable to expect that e-mail sent from one message transfer agent (MTA) to another is done over a TLS proto...

tls pgp forward-secrecy signal-protocol

Transcript for