7 ms·

So, how do people come up with these things? I assume every aspect of the design is carefully considered to defend it against various attacks. For example, why

So, how do people come up with these things? I assume every aspect of the design is carefully considered to defend it against various attacks. For example, why "right rotate 7 XOR right rotate 18 XOR right shift 3" and not "right rotate 2 XOR right rotate 3 XOR right shift 4"?

metalrain 5y ago
Visualized like this it feels like security through obscurity, but there must be reason for this. I did wonder why initialization is like: 1. Initialize hash value h0 to h7: first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19). 2. Initialize array of K constants: first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311
- manceraio 5y ago
  https://news.ycombinator.com/item?id=23166713 https://news.ycombinator.com/item?id=23166713 It seems like a "nothing up my sleeve" way to initialize the variables.
- deleted 5y ago
  [deleted]
- bsedlm 5y ago
  from what I've seen, there's a lot of "obscurity" to this; there are many seemingly arbitrary choices all over the place. In the end most encryption algorithms boil down to doing 'random' (arbitrary, hard to justify why) things to data and then undoing them exactly in order to decrypt. the math is all incredibly abstract but not all that complex, the high level of abstraction does make it quite difficult to grasp. What's worse is that I fear there are incentives (mostly political/security interests) to keep the field small and to keep many people far away from this very practical use for all these beautiful, elegant, simple (but extremely abstract) mathematics (refering to the entire cryptography field).
  - aaronmdjones 5y ago
    Not all decryption is doing exactly the same things in reverse. For example, with CTR mode (and thus GCM mode, which is CTR plus GMAC), you call the /encryption/ routine regardless of whether you're encrypting or decrypting data. This means in an embedded environment you can save die space because your program doesn't need the e.g. AES decryption routines too. https://upload.wikimedia.org/wikipedia/commons/4/4d/CTR_encryption_2.svg https://upload.wikimedia.org/wikipedia/commons/4/4d/CTR_encr... https://upload.wikimedia.org/wikipedia/commons/3/3c/CTR_decryption_2.svg https://upload.wikimedia.org/wikipedia/commons/3/3c/CTR_decr... (Note the bold text)
    - bsedlm 5y ago
      I mean it in the sense that they undo the 'noise' added to (or reverse the scrambling of) the initial input . even if they do it in a different way.
  - jjeaff 5y ago
    I doubt there is any concerted effort to keep the field small. That would be like saying tech companies don't want people learning how to code so that they can maintain an advantage. If anything, governments and companies are encouraging people to study cryptography so that they are able to hire more experts in the future. Now, once you get gatekeeper organizations and special licensing organizations like contractors licensing or beauticians licensing, those are examples of groups trying to keep the pool of experts small.
  - tptacek 5y ago
    This seems pretty silly, as there is extensive (one might say tedious) detail on why the decisions in a hash function or block cipher were made; your challenge is that you have to do a literature search to collect all the reasons --- but that's science for you.
  - holoduke 5y ago
    Isn't all the math involved in the end based on the modulo operator and prime numbers?
- orangepenguin 5y ago
  It's not security through obscurity. In fact, it's the very opposite. You can see the process exactly. The reason this is secure is because the process itself doesn't work backwards. You can create a hash using this algorithm, but you'll never reverse that hash back into the original text.
  - picture 5y ago
    I'm also wondering, how does this prevent preimaging attacks (or whatever they're called)? That is to say, what's stopping people from reliably producing output based on input?
    - skinkestek 5y ago
      > I'm also wondering, how does this prevent preimaging attacks (or whatever they're called)? First, see the Wikipedia entry about preimage attacks. Second, I am not a cryptographer but I think in practice there is a couple of things to be aware of: - make sure slightly different inputs have wildly different outputs - make sure no parts of the input survives - practically speaking there are an unlimited number of inputs that map to most (all? I'm not sure how uniform the distribution of sha256 is) output (since input is unlimited and output is a short string. - the classic preimage attack, rainbow tables, works because 1.) inputs, i.e. passwords, are often short and predictable - in ancient times password systems didn't use salts > That is to say, what's stopping people from reliably producing output based on input? I assume this should be the other way around, which is what I have tried to explain above. Again, read the Wikipedia page.
dragontamer 5y ago
1. You want an invertible operation. Invertible operations do _NOT_ lose information, and therefore have the maximum amount of entropy per step. 2. You want the invertible operation to pass a statistical test called "differential cryptography analysis". Over multiple rounds, it must be difficult / impossible to "predict" how 1-bit of difference changes the state. (ie: 1-bit of difference should lead to 50.0000000% change in every output bit. If its 50.1% or 49.9% change of bits, you fail because someone running cryptoanalysis will pick that up). ---------- #1 is somewhat easy. It turns out that Data XOR (Rotate-left Data) XOR (Rotate-right Data) is all you need to make an invertible operation. 5-operations, no more (any more is redundant and therefore unnecessary use of compute power), no less (any less is not invertible and therefore loses information / entropy each step). #2 is complicated: you gotta understand differential cryptoanalysis and run a bunch of tests. ----------- The discovery that (Data) XOR (Rotate-left Data) XOR (Rotate-right Data) was invertible became extremely popular in the 2010s through 2020s, and has become the cornerstone of XOR / Rotate / Add ciphers (aka: chacha), pseudorandom generators, and hash functions. I don't know quite when it was originally discovered, but Jenkins was blogging about the importance of invertibility and playing with invertible xor/rotate stuff in (non-crypto) hash functions way back in the 90s. I know Knuth's "Art of Computer Programming" book 2, Seminumerical Algorithms, discusses the importance of invertibility in random number generators, which is closely related to hashing / cryptographic procedures. So this "understanding" has been around for decades, but has only "become popular" in the SHA256 / Blake3 / pcg-random era. ------ In the 90s, ciphers were mostly using SBoxes for this step ("confusion", to grossly change a value to another value without losing information). But today, modern CPUs are much faster at add/xor/bitshift operations than reading/writing to memory. So SBoxes are no longer a high-speed methodology / primitive for these kinds of operations. It makes more sense to change our algorithms to use a new "invertible confusion operation" (aka: what SBoxes did before, and what ((Data) XOR (Rotate-left Data) XOR (Rotate-right Data)) does today). -------- EDIT: Remember: the modern crypto-primitive is just a combination of "confusion" principles and "diffusion" principles. 1. Confusion "lossless transforms" numbers into other numbers. (A "set permutation" of sorts) 2. Diffusion "moves" bits from one number into other numbers. Iterating over confusion + diffusion many times (IIRC, SHA256 is 64 rounds) is all you need to make a cryptographic cipher. If you "just" need a pseudo-random number generator or hash function, maybe 5 to 10 rounds is all you need.
kzrdude 5y ago
MD5 and SHA-1 are predecessors, and they are simpler, so certainly by starting from the understanding of the simpler ones. Just to say it wasn't all conceived in one go.
less_less 5y ago
You may not get an exact answer for SHA-1 or SHA-2, because they were designed by NSA, and I'm not sure whether a complete design doc has been published. SHA-3, by contrast, was designed in an open competition, and is completely different from SHA-1 and SHA-2. But here's a rough go at it. First of all, the overall form. SHA-2 is a Merkle-Damgård construction, meaning that it has a "compression function" which takes an algorithm state and a message block, and outputs a new algorithm state. The final block gets some padding, so that eg "x" and "x\000" don't have the same hash, and then the final algorithm state is the output. (This is a known weakness: from H(x) you can calculate H(x concat padding(x) concat other stuff). SHA-3 doesn't have this weakness. This weakness doesn't itself break collision resistance, but it can be dangerous for other uses of SHA2 if you aren't careful.) The compression function is a Davies-Meyer construction, which means that given an input state, it: * Copies the state. * Encrypts the state with a "cipher" of sorts (the "cipher" extracted from SHA-2 is known as SHACAL-2), using the message as a "key". * Adds the copied state to the encrypted state to produce a new state. Davies and Meyer proved that, for an ideal cipher, this would make a collision-resistant hash function. Note that because the update is a "cipher", it must be internally invertible. This is a good idea anyway, because any non-invertibility is by definition a collision, and you want to push that out as far as possible to make collisions hard to find. The step that isn't invertible is the final "add the copied state to the encrypted state". Within that design, the SHA-2 cipher is based on a shift register. Basic shift registers have been used in crypto for many decades; traditionally you get almost all of the bits in the register by shifting its current state, and at least one (typically only the one shifting in) by computing a function of the other bits. To extend this to general-purpose computers, you can do the same thing for words (32-bit words for SHA-224 and -256 and 64-bit words for SHA-384 -512). So you have A shifting to B shifting to C etc, with a final value that's computed and shifted back into A. You can see there's a slight twist, which is that instead of E=D you get E=D+stuff. I expect that this mitigates issues where the same stuff is used in the same way throughout the whole round. The "message schedule" is likewise based on a cipher's key schedule. The idea in a cipher is that each round needs a different version of the key to avoid "slide" attacks, so you mix the key during the round as well as mixing the cipher state. I'm not sure what the corresponding theory is for a hash function, but it's also pretty clear that you want a single byte of the message to be used in many places throughout the operation, so mixing the message is a must. For the operations, the biggest constraint is that they need to be as nonlinear as cheaply, because doing a bunch of linear functions in a row still gets you a linear function, and those are easy to break. They need to be nonlinear both as bits and as integers, so a popular design is to mix addition (linear over ints) with xor (linear over bits) and rotations (linear over both, but you need it to propagate changes from the top of a number to the bottom). That way the whole operation won't be linear over bits, nor over the integers, but all three operations are cheap on PCs. This is called an "ARX" (Add-Rotate-Xor) design. Picking the exact operations and rotation constants is something of a black art, and while you can trace descent from MD5-SHA0-SHA1-SHA2, the exact design criteria for the SHAs might not even be public. But you can see how some of the decisions may have been made. Consider the rotations in sigma0 and sigma1. The rotation constants in these designs are typically chosen so that if you look at any slice of the output, it will have many different input bits affecting it, which in turn means that small changes diffuse rapidly thoughout the design. This is not done perfectly in SHA2, in that the same bits are used for the Maj and Ch in successive iterations (i.e. you compute Maj(A,B,C) and then Maj(newA,A,B) next time since they shifted over), so you'd get correlated outputs of those steps from round to round, but apparently it's good enough. The setup constants are chosen as the square and cube roots of prime numbers, as "nothing-up-my-sleeve" numbers. The idea is that if the initialization were random numbers with no rationale given, then it would be a possible place that NSA could have hidden a backdoor. But it would be difficult to create a backdoor where the initialization is the square roots of the primes.
floodyberry- 5y ago
Generally, come up with a set of operations that you want to use that meet your design criteria (fast in hardware, fast in software, fast in SIMD, whatever), then brute-force the instruction order and/or arbitrary constants (rotations) to minimize known attacks and maximize diffusion e.g. the Chacha20 design document explains the choices made in a fairly high level and easy to understand way: https://cr.yp.to/chacha/chacha-20080128.pdf https://cr.yp.to/chacha/chacha-20080128.pdf
- dr_zoidberg 5y ago
  > (fast in hardware, fast in software, fast in SIMD, whatever) "Slow to compute in GPUs" has been another design criterion for a while. It helps against brute force attacks. Of course, you might want your hash to be fast on GPUs too, if you're trying to accelerate something, bu cryptographic hashes usually aim for attack resistance.
  - orra 5y ago
    I’m surprised that’s a design crtieria. Being able to calculate hashes quickly is advantageous. Speeding up hashing by, what, a few orders of magnitude shouldn’t break your ≥ 128 bits of preimage protection, surely?
    - jfindley 5y ago
      It depends what the goal of your hashing function is. Pure cryptographic hashes like sha256 want to be cheap to calculate. Slow on GPUs is only a design goal if you're making a password hash function, which is a rather different class of problem to sha256/chacha20 and similar. I think the commenter you're responding to got a little confused somewhere along the way and conflated cryptographic hashes with password hashing. EDIT: To be clear, password hashes are also cryptographic hashes - but they're a specific subclass of crypto hashes with different design criteria.
      - dr_zoidberg 5y ago
        Yes, I did confused the part about Keccak[0] being "slow" to compute without specfic hardware/extensions with it being slow on GPUs as a design goal. [0] Taking this as an example of newer crpytographic hashes, rather than the "old ones" that were easier/faster to calculate on GPUs.
tptacek 5y ago
It's helpful to understand that the algorithm wasn't designed the way it's presented in this illustration, and consists of somewhat discrete components. It's an iterated design, like a block cipher, meaning that it's built around a simple round function that's repeated a bunch of times on each input, rather than a super-complicated function run once. It belongs to a large, important family of cryptographic hashes called Merkle-Damgård, which pads messages to a fixed block size, chunks them into blocks, feeds and feeds each block to an iterated "compression function" (the heart of the hash) that takes a block and the chained n-1th compression value and spits out the nth compression value. So a lot of the mechanism in this illustration is just the vanilla mechanics of an MD hash. Iterated cryptographic designs generally have "schedule" or "expansion" functions that take the (small) input to the iterated function and "expand" it so that not all the iterations are working on exactly the same data; in the same way, a block cipher will have a "key schedule" that expands your 128-bit key into distinct "round keys" for each round. Message and key schedules, to me, feel like tiny little ciphers embedded in the larger cipher, and they're yet more of the complexity you're looking at, but can be studied independently (the SHA2 message schedule is apparently a big part of what makes it difficult to attack). When you see magic numbers in a block cryptography design like this, two relatively safe bets you can make is that they're either "nothing up my sleeve" numbers chosen from e.g. mathematical constants, just for the sake of avoiding arguments, or that they're the product of statistical testing to maximize things like diffusion or minimize things like linear or differential characteristics. With all block cipher cryptography one goal you always have is introducing nonlinearity; you can accidentally design a simple iterated function that is actually linear, and that cipher will be solvable simply with Gaussian elimination. People have shown me CTF levels that, for instance, linearized the AES round function. So when you see particular operations chained together in a cipher/hash design, keep in mind that they're balancing goals of (1) ensuring nonlinearity, (2) maximizing diffusion, the rate at which a single-bit change in the message totally scrambles the output in the shortest number of rounds, (3) optimizing metrics to avoid differential and linear cryptanalysis, (4) maximizing performance on target hardware. As was suggested downthread: a good way to come at this stuff is to start with MD4, and then read about MD5 (vs. MD4), then SHA1, and then take a closer look at SHA2. This stuff didn't get figured out all at once, and all these hashes are related. You might find MD4 easier to get your head around. For the linear and differential cryptanalysis stuff, which is surprisingly (given its age) important in cipher/hash design, a great starting point is the Heys tutorial, which is built around worked examples of both attacks: https://ioactive.com/wp-content/uploads/2015/07/ldc_tutorial.pdf https://ioactive.com/wp-content/uploads/2015/07/ldc_tutorial...
edflsafoiewq 5y ago
>why not "right rotate 2 XOR right rotate 3 XOR right shift 4" In this case, you generally want shifts that are far apart so bits that far apart have a chance to influence each other. The other operations have only local effects on bits (and, or, xor affect only the same bit position; add affects the same bit position and perhaps a few that follow via carries). Only the shifts/rotates give a chance for "non-local" effects.

metalrain 5y ago

Visualized like this it feels like security through obscurity, but there must be reason for this. I did wonder why initialization is like: 1. Initialize hash value h0 to h7: first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19). 2. Initialize array of K constants: first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311

manceraio 5y ago
https://news.ycombinator.com/item?id=23166713 https://news.ycombinator.com/item?id=23166713 It seems like a "nothing up my sleeve" way to initialize the variables.
deleted 5y ago
[deleted]
bsedlm 5y ago
from what I've seen, there's a lot of "obscurity" to this; there are many seemingly arbitrary choices all over the place. In the end most encryption algorithms boil down to doing 'random' (arbitrary, hard to justify why) things to data and then undoing them exactly in order to decrypt. the math is all incredibly abstract but not all that complex, the high level of abstraction does make it quite difficult to grasp. What's worse is that I fear there are incentives (mostly political/security interests) to keep the field small and to keep many people far away from this very practical use for all these beautiful, elegant, simple (but extremely abstract) mathematics (refering to the entire cryptography field).
- aaronmdjones 5y ago
  Not all decryption is doing exactly the same things in reverse. For example, with CTR mode (and thus GCM mode, which is CTR plus GMAC), you call the /encryption/ routine regardless of whether you're encrypting or decrypting data. This means in an embedded environment you can save die space because your program doesn't need the e.g. AES decryption routines too. https://upload.wikimedia.org/wikipedia/commons/4/4d/CTR_encryption_2.svg https://upload.wikimedia.org/wikipedia/commons/4/4d/CTR_encr... https://upload.wikimedia.org/wikipedia/commons/3/3c/CTR_decryption_2.svg https://upload.wikimedia.org/wikipedia/commons/3/3c/CTR_decr... (Note the bold text)
  - bsedlm 5y ago
    I mean it in the sense that they undo the 'noise' added to (or reverse the scrambling of) the initial input . even if they do it in a different way.
- jjeaff 5y ago
  I doubt there is any concerted effort to keep the field small. That would be like saying tech companies don't want people learning how to code so that they can maintain an advantage. If anything, governments and companies are encouraging people to study cryptography so that they are able to hire more experts in the future. Now, once you get gatekeeper organizations and special licensing organizations like contractors licensing or beauticians licensing, those are examples of groups trying to keep the pool of experts small.
- tptacek 5y ago
  This seems pretty silly, as there is extensive (one might say tedious) detail on why the decisions in a hash function or block cipher were made; your challenge is that you have to do a literature search to collect all the reasons --- but that's science for you.
- holoduke 5y ago
  Isn't all the math involved in the end based on the modulo operator and prime numbers?
orangepenguin 5y ago
It's not security through obscurity. In fact, it's the very opposite. You can see the process exactly. The reason this is secure is because the process itself doesn't work backwards. You can create a hash using this algorithm, but you'll never reverse that hash back into the original text.
- picture 5y ago
  I'm also wondering, how does this prevent preimaging attacks (or whatever they're called)? That is to say, what's stopping people from reliably producing output based on input?
  - skinkestek 5y ago
    > I'm also wondering, how does this prevent preimaging attacks (or whatever they're called)? First, see the Wikipedia entry about preimage attacks. Second, I am not a cryptographer but I think in practice there is a couple of things to be aware of: - make sure slightly different inputs have wildly different outputs - make sure no parts of the input survives - practically speaking there are an unlimited number of inputs that map to most (all? I'm not sure how uniform the distribution of sha256 is) output (since input is unlimited and output is a short string. - the classic preimage attack, rainbow tables, works because 1.) inputs, i.e. passwords, are often short and predictable - in ancient times password systems didn't use salts > That is to say, what's stopping people from reliably producing output based on input? I assume this should be the other way around, which is what I have tried to explain above. Again, read the Wikipedia page.

dragontamer 5y ago

1. You want an invertible operation. Invertible operations do _NOT_ lose information, and therefore have the maximum amount of entropy per step. 2. You want the invertible operation to pass a statistical test called "differential cryptography analysis". Over multiple rounds, it must be difficult / impossible to "predict" how 1-bit of difference changes the state. (ie: 1-bit of difference should lead to 50.0000000% change in every output bit. If its 50.1% or 49.9% change of bits, you fail because someone running cryptoanalysis will pick that up). ---------- #1 is somewhat easy. It turns out that Data XOR (Rotate-left Data) XOR (Rotate-right Data) is all you need to make an invertible operation. 5-operations, no more (any more is redundant and therefore unnecessary use of compute power), no less (any less is not invertible and therefore loses information / entropy each step). #2 is complicated: you gotta understand differential cryptoanalysis and run a bunch of tests. ----------- The discovery that (Data) XOR (Rotate-left Data) XOR (Rotate-right Data) was invertible became extremely popular in the 2010s through 2020s, and has become the cornerstone of XOR / Rotate / Add ciphers (aka: chacha), pseudorandom generators, and hash functions. I don't know quite when it was originally discovered, but Jenkins was blogging about the importance of invertibility and playing with invertible xor/rotate stuff in (non-crypto) hash functions way back in the 90s. I know Knuth's "Art of Computer Programming" book 2, Seminumerical Algorithms, discusses the importance of invertibility in random number generators, which is closely related to hashing / cryptographic procedures. So this "understanding" has been around for decades, but has only "become popular" in the SHA256 / Blake3 / pcg-random era. ------ In the 90s, ciphers were mostly using SBoxes for this step ("confusion", to grossly change a value to another value without losing information). But today, modern CPUs are much faster at add/xor/bitshift operations than reading/writing to memory. So SBoxes are no longer a high-speed methodology / primitive for these kinds of operations. It makes more sense to change our algorithms to use a new "invertible confusion operation" (aka: what SBoxes did before, and what ((Data) XOR (Rotate-left Data) XOR (Rotate-right Data)) does today). -------- EDIT: Remember: the modern crypto-primitive is just a combination of "confusion" principles and "diffusion" principles. 1. Confusion "lossless transforms" numbers into other numbers. (A "set permutation" of sorts) 2. Diffusion "moves" bits from one number into other numbers. Iterating over confusion + diffusion many times (IIRC, SHA256 is 64 rounds) is all you need to make a cryptographic cipher. If you "just" need a pseudo-random number generator or hash function, maybe 5 to 10 rounds is all you need.

kzrdude 5y ago

MD5 and SHA-1 are predecessors, and they are simpler, so certainly by starting from the understanding of the simpler ones. Just to say it wasn't all conceived in one go.

less_less 5y ago

You may not get an exact answer for SHA-1 or SHA-2, because they were designed by NSA, and I'm not sure whether a complete design doc has been published. SHA-3, by contrast, was designed in an open competition, and is completely different from SHA-1 and SHA-2. But here's a rough go at it. First of all, the overall form. SHA-2 is a Merkle-Damgård construction, meaning that it has a "compression function" which takes an algorithm state and a message block, and outputs a new algorithm state. The final block gets some padding, so that eg "x" and "x\000" don't have the same hash, and then the final algorithm state is the output. (This is a known weakness: from H(x) you can calculate H(x concat padding(x) concat other stuff). SHA-3 doesn't have this weakness. This weakness doesn't itself break collision resistance, but it can be dangerous for other uses of SHA2 if you aren't careful.) The compression function is a Davies-Meyer construction, which means that given an input state, it: * Copies the state. * Encrypts the state with a "cipher" of sorts (the "cipher" extracted from SHA-2 is known as SHACAL-2), using the message as a "key". * Adds the copied state to the encrypted state to produce a new state. Davies and Meyer proved that, for an ideal cipher, this would make a collision-resistant hash function. Note that because the update is a "cipher", it must be internally invertible. This is a good idea anyway, because any non-invertibility is by definition a collision, and you want to push that out as far as possible to make collisions hard to find. The step that isn't invertible is the final "add the copied state to the encrypted state". Within that design, the SHA-2 cipher is based on a shift register. Basic shift registers have been used in crypto for many decades; traditionally you get almost all of the bits in the register by shifting its current state, and at least one (typically only the one shifting in) by computing a function of the other bits. To extend this to general-purpose computers, you can do the same thing for words (32-bit words for SHA-224 and -256 and 64-bit words for SHA-384 -512). So you have A shifting to B shifting to C etc, with a final value that's computed and shifted back into A. You can see there's a slight twist, which is that instead of E=D you get E=D+stuff. I expect that this mitigates issues where the same stuff is used in the same way throughout the whole round. The "message schedule" is likewise based on a cipher's key schedule. The idea in a cipher is that each round needs a different version of the key to avoid "slide" attacks, so you mix the key during the round as well as mixing the cipher state. I'm not sure what the corresponding theory is for a hash function, but it's also pretty clear that you want a single byte of the message to be used in many places throughout the operation, so mixing the message is a must. For the operations, the biggest constraint is that they need to be as nonlinear as cheaply, because doing a bunch of linear functions in a row still gets you a linear function, and those are easy to break. They need to be nonlinear both as bits and as integers, so a popular design is to mix addition (linear over ints) with xor (linear over bits) and rotations (linear over both, but you need it to propagate changes from the top of a number to the bottom). That way the whole operation won't be linear over bits, nor over the integers, but all three operations are cheap on PCs. This is called an "ARX" (Add-Rotate-Xor) design. Picking the exact operations and rotation constants is something of a black art, and while you can trace descent from MD5-SHA0-SHA1-SHA2, the exact design criteria for the SHAs might not even be public. But you can see how some of the decisions may have been made. Consider the rotations in sigma0 and sigma1. The rotation constants in these designs are typically chosen so that if you look at any slice of the output, it will have many different input bits affecting it, which in turn means that small changes diffuse rapidly thoughout the design. This is not done perfectly in SHA2, in that the same bits are used for the Maj and Ch in successive iterations (i.e. you compute Maj(A,B,C) and then Maj(newA,A,B) next time since they shifted over), so you'd get correlated outputs of those steps from round to round, but apparently it's good enough. The setup constants are chosen as the square and cube roots of prime numbers, as "nothing-up-my-sleeve" numbers. The idea is that if the initialization were random numbers with no rationale given, then it would be a possible place that NSA could have hidden a backdoor. But it would be difficult to create a backdoor where the initialization is the square roots of the primes.

floodyberry- 5y ago

Generally, come up with a set of operations that you want to use that meet your design criteria (fast in hardware, fast in software, fast in SIMD, whatever), then brute-force the instruction order and/or arbitrary constants (rotations) to minimize known attacks and maximize diffusion e.g. the Chacha20 design document explains the choices made in a fairly high level and easy to understand way: https://cr.yp.to/chacha/chacha-20080128.pdf https://cr.yp.to/chacha/chacha-20080128.pdf

dr_zoidberg 5y ago
> (fast in hardware, fast in software, fast in SIMD, whatever) "Slow to compute in GPUs" has been another design criterion for a while. It helps against brute force attacks. Of course, you might want your hash to be fast on GPUs too, if you're trying to accelerate something, bu cryptographic hashes usually aim for attack resistance.
- orra 5y ago
  I’m surprised that’s a design crtieria. Being able to calculate hashes quickly is advantageous. Speeding up hashing by, what, a few orders of magnitude shouldn’t break your ≥ 128 bits of preimage protection, surely?
  - jfindley 5y ago
    It depends what the goal of your hashing function is. Pure cryptographic hashes like sha256 want to be cheap to calculate. Slow on GPUs is only a design goal if you're making a password hash function, which is a rather different class of problem to sha256/chacha20 and similar. I think the commenter you're responding to got a little confused somewhere along the way and conflated cryptographic hashes with password hashing. EDIT: To be clear, password hashes are also cryptographic hashes - but they're a specific subclass of crypto hashes with different design criteria.
    - dr_zoidberg 5y ago
      Yes, I did confused the part about Keccak[0] being "slow" to compute without specfic hardware/extensions with it being slow on GPUs as a design goal. [0] Taking this as an example of newer crpytographic hashes, rather than the "old ones" that were easier/faster to calculate on GPUs.

tptacek 5y ago

It's helpful to understand that the algorithm wasn't designed the way it's presented in this illustration, and consists of somewhat discrete components. It's an iterated design, like a block cipher, meaning that it's built around a simple round function that's repeated a bunch of times on each input, rather than a super-complicated function run once. It belongs to a large, important family of cryptographic hashes called Merkle-Damgård, which pads messages to a fixed block size, chunks them into blocks, feeds and feeds each block to an iterated "compression function" (the heart of the hash) that takes a block and the chained n-1th compression value and spits out the nth compression value. So a lot of the mechanism in this illustration is just the vanilla mechanics of an MD hash. Iterated cryptographic designs generally have "schedule" or "expansion" functions that take the (small) input to the iterated function and "expand" it so that not all the iterations are working on exactly the same data; in the same way, a block cipher will have a "key schedule" that expands your 128-bit key into distinct "round keys" for each round. Message and key schedules, to me, feel like tiny little ciphers embedded in the larger cipher, and they're yet more of the complexity you're looking at, but can be studied independently (the SHA2 message schedule is apparently a big part of what makes it difficult to attack). When you see magic numbers in a block cryptography design like this, two relatively safe bets you can make is that they're either "nothing up my sleeve" numbers chosen from e.g. mathematical constants, just for the sake of avoiding arguments, or that they're the product of statistical testing to maximize things like diffusion or minimize things like linear or differential characteristics. With all block cipher cryptography one goal you always have is introducing nonlinearity; you can accidentally design a simple iterated function that is actually linear, and that cipher will be solvable simply with Gaussian elimination. People have shown me CTF levels that, for instance, linearized the AES round function. So when you see particular operations chained together in a cipher/hash design, keep in mind that they're balancing goals of (1) ensuring nonlinearity, (2) maximizing diffusion, the rate at which a single-bit change in the message totally scrambles the output in the shortest number of rounds, (3) optimizing metrics to avoid differential and linear cryptanalysis, (4) maximizing performance on target hardware. As was suggested downthread: a good way to come at this stuff is to start with MD4, and then read about MD5 (vs. MD4), then SHA1, and then take a closer look at SHA2. This stuff didn't get figured out all at once, and all these hashes are related. You might find MD4 easier to get your head around. For the linear and differential cryptanalysis stuff, which is surprisingly (given its age) important in cipher/hash design, a great starting point is the Heys tutorial, which is built around worked examples of both attacks: https://ioactive.com/wp-content/uploads/2015/07/ldc_tutorial.pdf https://ioactive.com/wp-content/uploads/2015/07/ldc_tutorial...

edflsafoiewq 5y ago

>why not "right rotate 2 XOR right rotate 3 XOR right shift 4" In this case, you generally want shifts that are far apart so bits that far apart have a chance to influence each other. The other operations have only local effects on bits (and, or, xor affect only the same bit position; add affects the same bit position and perhaps a few that follow via carries). Only the shifts/rotates give a chance for "non-local" effects.