12 ms·

Every time one of these is posted, I’m expecting the steps to explain why they are being done. Like what makes this combination of operations have the particula

Every time one of these is posted, I’m expecting the steps to explain why they are being done. Like what makes this combination of operations have the particular properties we need?

Arnt 4y ago
AOL. It's like the articles that would explain how unix software by explaining in detail how to ./configured;make;make install and leave out everything specific to the software in question. I can explain one small part, though. A lot of these things need some fixed constants that have to be not all-zero, not all-one, not easily predictable and not someone's backdoor. So people will say things like "we need five ten-digit numbers here, so we'll use the second to eleventh digits of the square roots of the first five primes". That is, the use of the square root has nothing to do with being the square root of two, there's no deep math. The square root of two is just some number that you won't suspect of being a backdoor. https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
RcouF1uZ4gsC 4y ago
Exactly. Also SHA-256 is in the same family as MD-5. It would be nice to kind of go over how the family in general works, what weaknesses were discovered, and what changes were incorporated into SHA-256 that addresses these issues.
- abotsis 4y ago
  I’ve always been curious about whether it’s possible to have a collision when your input is 256 bits or less (in the case of sha256)… I even emailed Bruce Schneier. I got a polite response that he didn’t have time to look at it, which indicated to me he didn’t know “off the top of his head”, which I interpreted as “it’s not impossible”… but I still don’t know.
  - upofadown 4y ago
    What sort of collision? Or asking in a different way, what would you consider a collision?
    - _vdpp 4y ago
      2 messages producing the same digest. That’s actually a really interesting question.
    - mike_hock 4y ago
      I think he means a set-theoretical collision, not a feasible collision attack. I.e. "is SHA256 a bijection on 256-bit integers?"
  - edflsafoiewq 4y ago
    There are 2^257 - 1 inputs of 256 bits or less and only 2^256 possible hashes, so there must be a collision.
    - CamperBob2 4y ago
      The input is always padded out to 256 bits, though, isn't it?
      - edflsafoiewq 4y ago
        The input is padded to form a sequence of 512 bit chunks, but that doesn't change anything, padding is one-to-one so there's still the same number of inputs.
        Dylan16807 4y ago
        > padding is one-to-one so there's still the same number of inputs That part is debatable, if we imagine different padding schemes. If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash. You could also say you consider the extra '1' bit in SHA-256 as part of the payload, not truly 'padding' because it's mandatory, and make a similar argument, and it wouldn't be blatantly wrong.
        tialaramex 4y ago
        > That part is debatable, if we imagine different padding schemes. It isn't debatable because SHA-256 (and all these schemes) define the padding because it's necessary to have padding defeat the problem you're about to talk about and to do that they are in fact one-to-one: > If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash. As you might have guessed, this is not how it works. SHA-256 appends that "extra 1 bit" you talk about, then zeroes until it is 64-bits short of a multiple of 512 bits, and then a 64-bit count. So, as the earlier poster explained there are 2^257 -1 distinct hash inputs in abotsis' imagined set and thus there must be collisions by the pigeon hole principle, it really is that simple.
  - im3w1l 4y ago
    One way to think of hash functions is that the hash of any value is basically a random number. So we can consider what happens if the results were actually random, then what would be the probability of a collision? Consider a function from [0, 2^256 - 1] to [0, 2^256 - 1]. That is it maps 256bit numbers to 256bit numbers. It could in theory be represented as an enormous table lookup. Now how many such functions are there? Well there are 2^256 ways to map 0. And then 2^256 ways to map 1.. etc. We have 2^256 inputs we need to deal with each of which can give one of of 2^256 results. That turns into (2^256) ^ (2^256) Now, how many collision free functions are there? In this case there are 2^256 ways to map 0, but then we have to pick a different number for 1, so there are only 2^256 - 1 possiblites. Then 2^256 - 2 etc... It becomes (2^256)! where the exclamation mark is factorial. So the probability of no collisions is (2^256)! / [(2^256) ^ (2^256)]. It may not be obvious but that's a very small number. A little bit of intuition: let's say we fill out the values of our gigantic table by hand. Let's assume that by some miracle we filled out the first half without creating any collisions. Now that means we used up half the possible outputs. So every cell we fill out from now we have a 50/50 of creating a collision. And the further we get the more numbers are used up. Now sha256 is not a randomly chosen function. But without any evidence either way, we might suspect it does have collisions.
  - abotsis 4y ago
    To give some further context, I stumbled across this thought while reading how “community ids” are calculated. Community ids are commonly used to simplify joining/lookups for network security tools (suracata, zeek). They essentially concatenate the “quad tuple” (src ip/port, dest ip/port), and a “seed”, then run sha against it. I didn’t entirely understand the reason the authors chose sha (other than being security people who might have just reached for a crypto secure hash function). SHA is slow vs something like xxh, and given the number of sessions these things process, seemed like overkill. Further, it’s unclear to me what’s gained by using sha vs xxh or simply concatenating the bits. Then I started wondering about the downsides: whether it’s possible to have a false correlation because two sessions yielded the same sha digest.
pvg 4y ago
You're better off reading the Wikipedia page which covers things like that (for instance, the Merkle–Damgård construction) in some detail and without all the oversimplifications and almost unavoidable wrongness of slight write-ups like this.
- greggsy 4y ago
  On the contrary, I just want the dumbed down version. I’m not ever going to implement it (nobody should RYO crypto unless you really know what you’re doing), nor am I going to have to rely on the knowledge in my daily life - I’m not a maths educator, and I’m certainly not a cryptographer. It’s still good to understand the basics. I learnt a lot about PKI by forcing myself to learn the absolute basics of modulo, but I’ll never implement it or do a full calculation.
  - pvg 4y ago
    This isn't really a 'dumbed down version' and the person I'm replying to specifically asked about the sort of things not covered in this version.
userbinator 4y ago
There's some good discussion in the comments of another "one of these" a short while ago: https://news.ycombinator.com/item?id=30244534 https://news.ycombinator.com/item?id=30244534
tptacek 4y ago
You're not wrong. You're 100% right. This is like posting a story about how a game engine works, and having it be just blocks of assembly language with no explanation other than "here's some code multiplying a matrix, and then...".
- mewse 4y ago
  Geez, now I want to write an article about how a game engine works, explaining the rationale for every piece of it; I don't think I've ever seen somebody do that before. It's all kind of spread around in disparate bits and pieces, often quite hard to find (or even to know that you ought to be looking for it). Problem is that such a work would probably have to be more of a textbook, in terms of length and impenetrability. And it's not immediately obvious who the audience would be, as the vast majority of game developers these days are using pre-existing engines, rather than building new ones. But maybe there's still enough conceptual underpinnings that are worth discussing which would still be relevant for Unity/Unreal/Godot folks.
  - larusso 4y ago
    I think with most posts and also textbooks the problem is scope. I think the Handmade Hero project shows quite well what an amount of work it is to explain it. And there is the difference between a generic game engine like Unity and a specific engine for a specific project. And I mainly mean platform targeting and the likes. But I would read a blog post series :)
  - Sirenos 4y ago
    I think there is a middle ground. You can give a bird's eye view of the way things are done and a hand-wavy intuition for why they are done that way. Analogies go a long way towards building the latter. Then for those who want to dive deep, you can leave pointers to articles that cover such things in detail. It doesn't always have to be a choice between writing a book and nothing at all because the topic is too complex. I personally have benefited from bird's eye view blog posts and mini-articles more than I can remember. If you have the knowledge then go for it, someone out there will thank you.
  - 4y ago
lanecwagner 4y ago
huh, I didn't post this here, but I'm the author and kinda fun to just see it show up. Thanks for the feedback, it's a good point. I'll be making those updates soon.
- InCityDreams 4y ago
  Question: why didn't you post it to hn?
xiphias2 4y ago
Linear and differential cryptanalisis are the 2 classical way of breaking cryptographic hash functions, I think they are a cool way to learn about the importance of the current constructs being in use: https://alldifferences.net/difference-between-linear-and-differential-cryptanalysis/ https://alldifferences.net/difference-between-linear-and-dif... A simple way to look at them is this: if you change some specific bits in the input, maybe not all bits change by exacly 50% chance in the output, or they are not independent. For only a few rounds of S-Box-es you can probably find something like this by hand, for many rounds, SAT-solver or a special tool is needed.
- schoen 4y ago
  Can you help me understand how one might use a SAT solver to find ways in which cryptographic primitives (or their components) deviate from ideal pseudorandomness? I know what all of these things are, my intuition just isn't jumping to a way to formulate statistical correlations as a SAT problem.
dragontamer 4y ago
I wrote something up in a previous post. I'm no crypto-expert. But I did study it a bit. https://news.ycombinator.com/item?id=30248439 https://news.ycombinator.com/item?id=30248439 Obviously, any actual crypto-experts can feel to correct me if I got history and/or understanding incorrect here. ----- Addenendum to my previous post. 1. Confusion -- Bytes should turn into other bytes in random-looking ways. For example, the byte 0x25 may turn into 0x88. Aka: S-boxes in 90s-era ciphers. 2. Diffusion -- Bit-changes should "spread" to as many bits as possible. 3. Invertible -- Invertible operations minimizes the loss of information. Encryption/Decryption must be invertible by definition, but even Hash-functions should be largely built out of invertible operations. Try to make confusion and/or diffusion steps invertible. 4. ADD / XOR / Shift / Rotate -- These operations are the more popular way to make Invertible Confusion/Diffusion functions today. 5. SBox + Galois Fields -- For AES (a 90s-era algorithm), SBox was the source of confusion, and Galois Field arithmetic was the source of Diffusion. I could explain why but that gets more complicated. 5. Testing -- Test your functions against linear cryptography (how is the input related to the output?) and differential cryptography (how is each input bit related to each output bit on a bit-by-bit basis?) ------ Obviously, hash functions (like SHA256) must be non-invertible by the end of it all. But you want to carefully think about where the source of non-invertibility comes from, and to minimize the loss of entropy/information at any particular step. With these principles, its not very hard to make your own hash function. I'd suggest studying Bob Jenkin's "JOAAT" hash, just-one-at-a-time. Its a non-crypto hash, but it is probably one of the simplest hashes that uses the above principles: https://en.wikipedia.org/wiki/Jenkins_hash_function https://en.wikipedia.org/wiki/Jenkins_hash_function
- xmprt 4y ago
  What differentiates a non-crypto hash from a crypto hash. Is there a fundamental difference between the two which prevents one from being used for cryptographic purposes?
  - l33t2328 4y ago
    Yes! We’d like our cryptographic hash functions to be collision resistant and preimage resistant. That is, we’d like it to be hard to generate 2 different messages m1 and m2 where the hash of m1 is equal to the hash of m2, and we’d also like for it to be hard to compute any function of the message m(except the hash of m) if you’re given only the hash of m. Non cryptographic hash functions don’t require these properties, and in fact some hashing algorithms used for data mining are designed to, for example, map near inputs to near outputs.
can16358p 4y ago
Came here to ask the same. I enjoyed the blog, yet as a non-cryptographer, I'd like to see the reasons behind the actions: e.g. Okay we right rotate that input, but why are we doing this? Or Why are we taking cube roots of 64 primes? etc.
- edflsafoiewq 4y ago
  > Why are we taking cube roots of 64 primes? https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
  - can16358p 4y ago
    That was helpful. It'd be great if there are tips like these (even Wikipedia links like this is very helpful) are also present in the posts like the blog post.

Every time one of these is posted, I’m expecting the steps to explain why they are being done. Like what makes this combination of operations have the particular properties we need?

Arnt 4y ago

AOL. It's like the articles that would explain how unix software by explaining in detail how to ./configured;make;make install and leave out everything specific to the software in question. I can explain one small part, though. A lot of these things need some fixed constants that have to be not all-zero, not all-one, not easily predictable and not someone's backdoor. So people will say things like "we need five ten-digit numbers here, so we'll use the second to eleventh digits of the square roots of the first five primes". That is, the use of the square root has nothing to do with being the square root of two, there's no deep math. The square root of two is just some number that you won't suspect of being a backdoor. https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number

RcouF1uZ4gsC 4y ago

Exactly. Also SHA-256 is in the same family as MD-5. It would be nice to kind of go over how the family in general works, what weaknesses were discovered, and what changes were incorporated into SHA-256 that addresses these issues.

abotsis 4y ago
I’ve always been curious about whether it’s possible to have a collision when your input is 256 bits or less (in the case of sha256)… I even emailed Bruce Schneier. I got a polite response that he didn’t have time to look at it, which indicated to me he didn’t know “off the top of his head”, which I interpreted as “it’s not impossible”… but I still don’t know.
- upofadown 4y ago
  What sort of collision? Or asking in a different way, what would you consider a collision?
  - _vdpp 4y ago
    2 messages producing the same digest. That’s actually a really interesting question.
  - mike_hock 4y ago
    I think he means a set-theoretical collision, not a feasible collision attack. I.e. "is SHA256 a bijection on 256-bit integers?"
- edflsafoiewq 4y ago
  There are 2^257 - 1 inputs of 256 bits or less and only 2^256 possible hashes, so there must be a collision.
  - CamperBob2 4y ago
    The input is always padded out to 256 bits, though, isn't it?
    - edflsafoiewq 4y ago
      The input is padded to form a sequence of 512 bit chunks, but that doesn't change anything, padding is one-to-one so there's still the same number of inputs.
      - Dylan16807 4y ago
        > padding is one-to-one so there's still the same number of inputs That part is debatable, if we imagine different padding schemes. If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash. You could also say you consider the extra '1' bit in SHA-256 as part of the payload, not truly 'padding' because it's mandatory, and make a similar argument, and it wouldn't be blatantly wrong.
        tialaramex 4y ago
        > That part is debatable, if we imagine different padding schemes. It isn't debatable because SHA-256 (and all these schemes) define the padding because it's necessary to have padding defeat the problem you're about to talk about and to do that they are in fact one-to-one: > If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash. As you might have guessed, this is not how it works. SHA-256 appends that "extra 1 bit" you talk about, then zeroes until it is 64-bits short of a multiple of 512 bits, and then a 64-bit count. So, as the earlier poster explained there are 2^257 -1 distinct hash inputs in abotsis' imagined set and thus there must be collisions by the pigeon hole principle, it really is that simple.
- im3w1l 4y ago
  One way to think of hash functions is that the hash of any value is basically a random number. So we can consider what happens if the results were actually random, then what would be the probability of a collision? Consider a function from [0, 2^256 - 1] to [0, 2^256 - 1]. That is it maps 256bit numbers to 256bit numbers. It could in theory be represented as an enormous table lookup. Now how many such functions are there? Well there are 2^256 ways to map 0. And then 2^256 ways to map 1.. etc. We have 2^256 inputs we need to deal with each of which can give one of of 2^256 results. That turns into (2^256) ^ (2^256) Now, how many collision free functions are there? In this case there are 2^256 ways to map 0, but then we have to pick a different number for 1, so there are only 2^256 - 1 possiblites. Then 2^256 - 2 etc... It becomes (2^256)! where the exclamation mark is factorial. So the probability of no collisions is (2^256)! / [(2^256) ^ (2^256)]. It may not be obvious but that's a very small number. A little bit of intuition: let's say we fill out the values of our gigantic table by hand. Let's assume that by some miracle we filled out the first half without creating any collisions. Now that means we used up half the possible outputs. So every cell we fill out from now we have a 50/50 of creating a collision. And the further we get the more numbers are used up. Now sha256 is not a randomly chosen function. But without any evidence either way, we might suspect it does have collisions.
- abotsis 4y ago
  To give some further context, I stumbled across this thought while reading how “community ids” are calculated. Community ids are commonly used to simplify joining/lookups for network security tools (suracata, zeek). They essentially concatenate the “quad tuple” (src ip/port, dest ip/port), and a “seed”, then run sha against it. I didn’t entirely understand the reason the authors chose sha (other than being security people who might have just reached for a crypto secure hash function). SHA is slow vs something like xxh, and given the number of sessions these things process, seemed like overkill. Further, it’s unclear to me what’s gained by using sha vs xxh or simply concatenating the bits. Then I started wondering about the downsides: whether it’s possible to have a false correlation because two sessions yielded the same sha digest.

pvg 4y ago

You're better off reading the Wikipedia page which covers things like that (for instance, the Merkle–Damgård construction) in some detail and without all the oversimplifications and almost unavoidable wrongness of slight write-ups like this.

greggsy 4y ago
On the contrary, I just want the dumbed down version. I’m not ever going to implement it (nobody should RYO crypto unless you really know what you’re doing), nor am I going to have to rely on the knowledge in my daily life - I’m not a maths educator, and I’m certainly not a cryptographer. It’s still good to understand the basics. I learnt a lot about PKI by forcing myself to learn the absolute basics of modulo, but I’ll never implement it or do a full calculation.
- pvg 4y ago
  This isn't really a 'dumbed down version' and the person I'm replying to specifically asked about the sort of things not covered in this version.

userbinator 4y ago

There's some good discussion in the comments of another "one of these" a short while ago: https://news.ycombinator.com/item?id=30244534 https://news.ycombinator.com/item?id=30244534

tptacek 4y ago

You're not wrong. You're 100% right. This is like posting a story about how a game engine works, and having it be just blocks of assembly language with no explanation other than "here's some code multiplying a matrix, and then...".

mewse 4y ago
Geez, now I want to write an article about how a game engine works, explaining the rationale for every piece of it; I don't think I've ever seen somebody do that before. It's all kind of spread around in disparate bits and pieces, often quite hard to find (or even to know that you ought to be looking for it). Problem is that such a work would probably have to be more of a textbook, in terms of length and impenetrability. And it's not immediately obvious who the audience would be, as the vast majority of game developers these days are using pre-existing engines, rather than building new ones. But maybe there's still enough conceptual underpinnings that are worth discussing which would still be relevant for Unity/Unreal/Godot folks.
- larusso 4y ago
  I think with most posts and also textbooks the problem is scope. I think the Handmade Hero project shows quite well what an amount of work it is to explain it. And there is the difference between a generic game engine like Unity and a specific engine for a specific project. And I mainly mean platform targeting and the likes. But I would read a blog post series :)
- Sirenos 4y ago
  I think there is a middle ground. You can give a bird's eye view of the way things are done and a hand-wavy intuition for why they are done that way. Analogies go a long way towards building the latter. Then for those who want to dive deep, you can leave pointers to articles that cover such things in detail. It doesn't always have to be a choice between writing a book and nothing at all because the topic is too complex. I personally have benefited from bird's eye view blog posts and mini-articles more than I can remember. If you have the knowledge then go for it, someone out there will thank you.
- 4y ago

lanecwagner 4y ago

huh, I didn't post this here, but I'm the author and kinda fun to just see it show up. Thanks for the feedback, it's a good point. I'll be making those updates soon.

InCityDreams 4y ago
Question: why didn't you post it to hn?

xiphias2 4y ago

Linear and differential cryptanalisis are the 2 classical way of breaking cryptographic hash functions, I think they are a cool way to learn about the importance of the current constructs being in use: https://alldifferences.net/difference-between-linear-and-differential-cryptanalysis/ https://alldifferences.net/difference-between-linear-and-dif... A simple way to look at them is this: if you change some specific bits in the input, maybe not all bits change by exacly 50% chance in the output, or they are not independent. For only a few rounds of S-Box-es you can probably find something like this by hand, for many rounds, SAT-solver or a special tool is needed.

schoen 4y ago
Can you help me understand how one might use a SAT solver to find ways in which cryptographic primitives (or their components) deviate from ideal pseudorandomness? I know what all of these things are, my intuition just isn't jumping to a way to formulate statistical correlations as a SAT problem.

dragontamer 4y ago

I wrote something up in a previous post. I'm no crypto-expert. But I did study it a bit. https://news.ycombinator.com/item?id=30248439 https://news.ycombinator.com/item?id=30248439 Obviously, any actual crypto-experts can feel to correct me if I got history and/or understanding incorrect here. ----- Addenendum to my previous post. 1. Confusion -- Bytes should turn into other bytes in random-looking ways. For example, the byte 0x25 may turn into 0x88. Aka: S-boxes in 90s-era ciphers. 2. Diffusion -- Bit-changes should "spread" to as many bits as possible. 3. Invertible -- Invertible operations minimizes the loss of information. Encryption/Decryption must be invertible by definition, but even Hash-functions should be largely built out of invertible operations. Try to make confusion and/or diffusion steps invertible. 4. ADD / XOR / Shift / Rotate -- These operations are the more popular way to make Invertible Confusion/Diffusion functions today. 5. SBox + Galois Fields -- For AES (a 90s-era algorithm), SBox was the source of confusion, and Galois Field arithmetic was the source of Diffusion. I could explain why but that gets more complicated. 5. Testing -- Test your functions against linear cryptography (how is the input related to the output?) and differential cryptography (how is each input bit related to each output bit on a bit-by-bit basis?) ------ Obviously, hash functions (like SHA256) must be non-invertible by the end of it all. But you want to carefully think about where the source of non-invertibility comes from, and to minimize the loss of entropy/information at any particular step. With these principles, its not very hard to make your own hash function. I'd suggest studying Bob Jenkin's "JOAAT" hash, just-one-at-a-time. Its a non-crypto hash, but it is probably one of the simplest hashes that uses the above principles: https://en.wikipedia.org/wiki/Jenkins_hash_function https://en.wikipedia.org/wiki/Jenkins_hash_function

xmprt 4y ago
What differentiates a non-crypto hash from a crypto hash. Is there a fundamental difference between the two which prevents one from being used for cryptographic purposes?
- l33t2328 4y ago
  Yes! We’d like our cryptographic hash functions to be collision resistant and preimage resistant. That is, we’d like it to be hard to generate 2 different messages m1 and m2 where the hash of m1 is equal to the hash of m2, and we’d also like for it to be hard to compute any function of the message m(except the hash of m) if you’re given only the hash of m. Non cryptographic hash functions don’t require these properties, and in fact some hashing algorithms used for data mining are designed to, for example, map near inputs to near outputs.

can16358p 4y ago

Came here to ask the same. I enjoyed the blog, yet as a non-cryptographer, I'd like to see the reasons behind the actions: e.g. Okay we right rotate that input, but why are we doing this? Or Why are we taking cube roots of 64 primes? etc.

edflsafoiewq 4y ago
> Why are we taking cube roots of 64 primes? https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
- can16358p 4y ago
  That was helpful. It'd be great if there are tips like these (even Wikipedia links like this is very helpful) are also present in the posts like the blog post.