SHA possible backdoor by NSA and how we improve that

[Xiitech]

Hi there,

part of text from our website:

"Prime numbers have patterns and rules, maybe NSA uses that for making hash functions with "tunnel" (making (bits rotate, bits shift, bits xor and add input) function which dont break rule in every iteration). Tunel is rule which can, for specific output in hash function, predicts field of possible inputs or field of impossible inputs (like Beal conjecture) and dramatically reduce speed of brute force attack. Theoretically, this is possible only if NSA knows secret (unpublished) rules similar to Beal conjecture etc, (Why NSA everytime uses primes for making hash functions?  )''

more on https://www.xiitech.net/p/sha256.html

What do you think about this?  

[1713969300]

1713969300

[1713969300]

1713969300

[DannyHamilton]

- snip -
Prime numbers have patterns and rules, maybe NSA uses that for making hash functions
- snip -
(Why NSA everytime uses primes for making hash functions?)
- snip -

Nonsense and FUD.

There are no prime numbers used in the SHA256 hash function.

[HeRetiK]

- snip -
Prime numbers have patterns and rules, maybe NSA uses that for making hash functions
- snip -
(Why NSA everytime uses primes for making hash functions?)
- snip -

Nonsense and FUD.

There are no prime numbers used in the SHA256 hash function.

Even if it were true, that would only mean that the NSA could create some badass ASIC miners. At this point in time Bitcoin's PoW hashing algorithm is probably the least viable attack vector (one could argue that the arrival of ASICs already was an successful "attack" on SHA256 as PoW hashing algorithm in the first place).

[s2]

The fact that we've not seen vastly more powerful miners appear is proof this would not work (and that time travel can't work). 

That agency no doubt has a vast amount of talent but they don't represent the entire world, someone with a laptop in Russia/Japan/Mauritius who's not working there but also dedicated their life to mathematics/cryptography would have cashed in on any weakness if it existed.

Also SHA256 doesn't use primes that I'm aware of, it's all simple bit shifting logic.

[aleksej996]

SHA algorithms have been public for a long time, by now someone would likely found out and publish it. Thanks to Bitcoin there is a financial incentive for it as well, so the odds are against it. I think it is quite hard, even for NSA, to hide something like that in plain sight for so long.

[cleavey]

The more widely used an algorithm is, the more secure in the knowledge we can be that it is secure. When something is adopted as widely as SHA256 is, people constantly test it for weaknesses. It's likely in the future that an attack will reduce the complexity of creating a collision, but if an attack gets anywhere close to viable, people will just change the algorithm they use.

[currypto]

- snip -
Prime numbers have patterns and rules, maybe NSA uses that for making hash functions
- snip -
(Why NSA everytime uses primes for making hash functions?)
- snip -

Nonsense and FUD.

There are no prime numbers used in the SHA256 hash function.

1. Yes
2. No

There are prime numbers in SHA256. Look at the NIST paper. It is set K, which uses the first 64 primes.

But the whole purpose of using primes is to prove "nothing is up my sleeve". That is literally their sole purpose. The creators of SHA256 could have used other irrational numbers and then maybe...that would cause concern.

Lol, the suggested "fix" is pretty funny...

...with commonly known numbers like birthdays of famous people in 1962.

[DannyHamilton]

There are prime numbers in SHA256. Look at the NIST paper. It is set K, which uses the first 64 primes.

But the whole purpose of using primes is to prove "nothing is up my sleeve". That is literally their sole purpose. The creators of SHA256 could have used other irrational numbers and then maybe...that would cause concern.

You are correct.  I was thinking about the iteration steps and forgot about the initialization.  I've updated my post.

[jonnylatte]

Every SHA round the hash function throws away information. That is there are more inputs to the round than there are uniquely determined outputs, each round is not reversible in the formal sense. If you wanted to reverse this process you would have to guess what this information is that has been thrown away. You cant just guess any arbitrary set of bits though because when you reverse back to the start of the rounds you have to generate the magic number or you will have an impossible starting value for the function and you cant set enough of the bits in the step just before to generate the magic number because there is only so  much thrown away each round that can be guessed at in reversal. The effect of this is that you need to be guessing at the right bits throughout all of the process and the complex mathematical relationship you have to solve becomes unpractical to solve with current known techniques.

Now what of the values of the magic numbers? well they could all be zero as far as I am concerned. You still have to do the same amount of work guessing the bits that are thrown away in every round to generate a string of zeros or a string of prime numbers or what have you. If you had complete freedom to set the magic numbers and the inputs you could make a sha function that hashes to any chosen value, you just have to reverse the function and then decree that whatever value you have in the magic numbers are the magic numbers so its important that these values are fixed and for the sake of not being able to determine that one hash value, not something that is completely arbitrary and unexplained.

Prime numbers seem as good as anything because it is highly unlikely that they are the garden of Eden state of some specific hash that the developers of the algorithm wanted to be able to generate. It is possible that there is some deeper mathematical relationship between the numbers and the hash algorithm itself but that relationship would also have to be shared with the input data because it is part of the same uniform mathematical process involved in a round.