The Side Channel

4:45 AM

I see it as two (basically) orthogonal properties. Vulnerability of SHA-1 to a collision attack, vs, exploitability of X given a collision for Y. The former is a property of SHA-1. The latter is more of a property of file format X than a property of hash function Y.

If SHA-1 were a function that was only specified to work with particular file formats then I would consider the (non)exploitability relevant, but since it's meant to work for arbitrary bit strings I don't see it as relevant in this context.

5:05 AM

I'd bet that there are multiple "Is a collision attack really an attack if it requires junk data blocks?" questions on this site. That's something that crypto newbies on the internet often get hung up on. I think their logic is "I can't choose any arbitrary value in creating a collision, therefore the content of the blocks which are different is random. If I insert a random 64 byte into a ___ file then the file becomes corrupted."

"(Because whenever I tried it the program I used to open it either gave me an error message or crashed the application.) Therefore it's actually safe to use MD5 in my specific project."

And that's made even worse because people assume far too frequently that there doesn't exist enough freedom in a file format to exploit a collision. I guess that they think of the difference injected is basically equivalent to file corruption.

These people are naive enough to, for example, say that a collision attack isn't really a vulnerability because it wouldn't be possible to create an exploitable difference in a file format as complex as executable binary. (Executables are the example they go to. I'm not making that up.)

These people, even though they're programmers overlook something as simple as doing something like if (checksum(ptr) == someConstant) doBenignThing(); else doMaliciousThing();

They kind of see collision attacks (wrongly) like we would the 2^126 attack on AES-128. Purely "academic" because it's so impractical.

So pick your favorite reason to change that sentence. Pedantic concern. Mathematical precision. Or common and dangerous misconception.

I think newbies also have some collision vs 2nd preimage attack confusion there, besides just thinking a collision attacks doesn't count if an attack isn't powerful enough for a hacker to create whatever collision they want.

5:55 AM

Ha. One last thought for tonight. Usually people are exposed first to the "changing a few bits of input causes a big change to output bits" idea of hash functions before a more nuanced definition. I wonder if they assume the reverse. "Small changes in output bits means you have to make drastic changes to inputs." :)

9:08 AM

Sometimes I wonder what the people doing the typesetting for Springer are thinking. Where would you get the idea that "San Francisco" should be changed to "San Franiso"?

10:29 AM

@FutureSecurity I've updated my answer. When you have time, please check.

4:28 PM

Actually, I don't think I've seen a single question of the form "Is a collision attack really an attack if it requires junk data blocks?"

The problem is the difference between the theoretical and practical collision attack.
In thoery, it is a collision attack since we found the evidence.
In practice, show me a case for it.
and, Google's team made for both of it.

5:22 PM

Oh. That part is in response to a comment. I think I would have omitted that part if it were my answer because it's not directly relevant to MACs and is potentially confusing. A hypothetical collision attack on some function H wouldn't break HMAC-H or H(key || message).

What's required from a MAC algorithm are the security properties of a PRF. You can add collision resistance if you need to for a certain application, but it's optional. A reasonable hash based PRF probably inherits collision resistance from its underlying hash function.

A collision attack doesn't effect vanilla MAC security. Someone that doesn't know the key can't exploit a collision attack to forge messages. Someone that does know the key can trivially "forge" messages but that doesn't matter for generic a MAC.

1. A MAC is not necessarily a PRF. It's the other way round.

2. A collision attack can break H(k||m). It just doesn't necessarily do so.

Why 1? Is it MACs are a superset of PRFs because PRFs assume uniformity?

5:39 PM

Yes. Take any Mac and change it by always appending a 0 to the tag. The result is still a Mac but certainly not a PRF.

The relevant security definition for Macs is (strong) existential unforgeability under chosen message attacks.

5:59 PM

Also Macs are not necessarily required to be deterministic. So they do not even have to define a family of functions over the message space.

@Maeher Do you happen to be well versed with entropy? This question (and many others like it) could really use proper answers from someone who actually knows the definitions...

We used to have Squeamish Ossifrage for that, but they're long gone

I suspect that question may be destined to become a HNQ

6:22 PM

Yes, it has potential. By the way the password question of Information security still HNQ. reached 40000 views in 6 days

I came up with the definition that entropy is "a measure of unknown information". Feedback would be appreciated.

The faults I've come up with are A) The term information is sort of vague and sort of circular and B) It's not clear that entropy is a property of a process, not a single random sample.

"Notice that the entropy is a property of the generator, not that of one particular bitstring that it outputs."

@fgrieu How about instead of "generator" say "property of the seed"?

6:39 PM

Exactly, I upvoted fgrieu's answer

"generation process", maybe

It is now HNQ

But he still writes :)

I knew it would be >.<

After days finally we have one.

"Why do we require requires requires?" is a question from the main site. Clickbait titles are part of another class of HNQs

That's exactly how you get a HNQ

it's not about the content/quality of the question, it's about how many clicks you can get

6:46 PM

That or it's a question lots of people think they can answer and answer better.

Exactly. The more answers and comments the more to be HNQ

another answer

lol

I'm wondering if protecting the question is a good idea

Probably. I don't know how it works though.

Let it be free :)

6:58 PM

What I kind of like about my "amount of unknown information" definition is how it simply bridges the gap between how we use the term with respect to cryptography and metaphysical information. The danger is that it's over simplified or just wrong.

Like the difference between a D6 roll made in public having 0 bits of information vs 2.58 bits. Tomorrow's NIST randomness beacon (pretending it's working then) publication each have a certain amount of information. But the moment they are published the entropy goes down to zero bits for the purpose of key generation.

It's understandable by people who are only ever going to hear about information theory entropy in the context of passwords. (It lets them understand why their super secret password generating scheme which produces passwords like "b7Al8gk.gmail" and "b7Al8gk.facebook" doesn't have more entropy "b7Al8gk" does.)

And also is compatible with how information theory is used in compression algorithms. It explains why you only need 8 bits to compress a file format which is always a fixed 1kb header followed by a single random byte, and not closer to 1028 bits. (Also why general purpose compression algorithms perform differently than specialized ones.)

Bleh. My brain, typing stubs, and seeing orbs aren't working together well today. I think you all get the idea, though.

@Maeher Can you pick apart that def?

Entropy (information theory)

8:44 PM

at least that Q settled down

suigin

10:20 PM

As the length of a sequence grows without bound, its minimum entropy and
Shannon entropy converge to exactly 1 bit per output bit. Is that not correct?

@FutureSecurity I @ forgot. sorry

SEJPM

@suigin entropy is a property of the generating process, so the length shouldn't matter

suigin

Minimum length not required to prove statistical minimum? I will consider.

Cryptography talk different from mathematics. I am trying to sort words. Thank you.

SEJPM

Information entropy is the average rate at which information is produced by a stochastic source of data. The measure of information entropy associated with each possible data value is the negative logarithm of the probability mass function for the value: S = − ∑ i P i log ⁡ P i S=-\sum _{i}P_{i}\log {P_{i}} . When the data source has a lower-probability value (i.e., when...

(this should immediately link to the precise definition, which only talks about random variables)

and ideally your estimators for the entropy variants should converge against the real values for infinite sample sequences

and indeed both should approach 1 for a uniformly random distribution

suigin

I am familiar with maths. I am learning assumptions. There was a "no" for my paper to cryptography with hardware. There was best paper theory with maths. I am hope that I learn. Sorry English, and thank you. I will read more questions.

11:03 PM

@suigin There isn't a good reason to care about entropy per bit or per byte of output. It isn't a commodity. It's not like a pile of dirt.

Also entropy isn't like a chemical. There isn't good reason to model it analogous to something you could dilute by adding water.

The math always give you the right answer. For each possible outcome figure out the probability of that outcome happening. Then use the equation for Shannon entropy.

When the math doesn't give you the same answer as your intuition then your intuition is wrong. (Or your arithmetic. But not the equation defining Shannon entropy.)

A recent [eprint paper](https://eprint.iacr.org/2019/029) claims to bound $\lambda_1(\Lambda^\perp(\mathbf{A})) = O(1)$ over uniform choice of $\mathbf{A}\in\mathbb{Z}^{n\times m}$. They derive a bound specifically of 4. This has applications to solving $\mathsf{SIS}_{n,m,q,4}$ in $\mathsf{P}$.

I'm no expert in this area, but it seems to me this contradicts the common thought that $\lambda_1(\Lambda^\perp(\mathbf{A})) = \Omega(\sqrt{n\log q})$ (see, for example, section 2.4.2 of [this paper](https://web.eecs.umich.edu/~cpeikert/pubs/shorter.pdf)).

Entropy is not diluted, depleted, or rationed. It is the property of a stochastic process. Not a property of a string or of a single sample from a statistical distribution.

I was just about to leave. I'll take a look at that later if someone else doesn't get to it first, Mark.

Thanks!

11:22 PM

If that paper is correct it seems like kind of a big deal :o

Yeah, but the (seeming) contradiction to prior work and lack of experimental evidence that it's correct (At least I've never heard that whp over uniform choice of matrices that $\lambda_1(\Lambda^\perp(\mathbf{A})) = \leq 4$, and I feel like that should become obvious experimentally even early on) makes me think it isn't true. Of course, then I run into the issue that looking through it I don't see any obvious errors, and I haven't worked with the hardness of $\mathsf{SIS}$ before.

11:39 PM

@Mark if you can find a more objective way to ask about it, it might make a good question for the site. It's true that "discuss this" type of questions are not appropriate, but typically it's possible to find a specific question with a definite answer. As for places where discussion is appropriate, mailing lists leap to mind, in particular the one for NIST's post-quantum project

Since there are so many lattice-based schemes submitted to that, any paper that shakes the foundations of all lattice cryptography is bound to receive attention and serious scrutiny there

I wouldn't be surprised if it was already being discussed in such circles

Is there a list of relevant mailing lists somewhere? I'm a new PhD student, and just recently (while searching for stuff related to this paper lol) realized that they exist/are still used

Is there info on how to join the NIST mailing list without visiting NIST? The website is still down due to the gov shutdown

If there is such a list, I don't know of it (I'm not a user of any mailing lists though)

gosh, that's a good question

I think it involves emailing a special address

you could try archive.org maybe

Archive doesn't have it

dang, that was my best guess

I expect that it requires emailing something as well. Google has an email in the preview text, but I expect that email is for mailing the entire list and don't want to risk it