Topic: The precise status of the relevant number theoretic problems for SHA-256 (Read 3846 times)

Please do not believe for a second that SHA256 is unbreakable. It is unbroken, as far as we know, but there are no mathematical proofs showing it is unbreakable and without that it is reasonable to conclude it can and will eventually be broken.  It makes a great deal of sense that SHA256 would have a back-door, and I believe that the choosing of these constants is a major clue.  If you are familiar with the π(), PI, function, also known as the prime counting function, you will see this function has not yet been completely solved, but it can be proven that if solved, the function can be used to solve P(n) where P is the function that produces the nth prime.  While the π() has not been solved, there are extremely close approximations that have been contrived which follow the exact value of π() for some number of digits before curling away from it.  I went down a rabbit hole on this under the false impression that ln(x) approaches  π(x) as x approaches infinity trying to create a curl adjustment function based on this fact in such a way that the curl would meet ln(x) at some logarithmic scale of x.  While I may have failed at solving the π(x) function my research shows that it is extremely likely that P(n) can be approximated with another function for small values of n (such as 72 used by SHA256).  I also want to note there is nothing particularly special about the rightshift function, it is simply floor(x/2^n) where n is the number of digits shifted.  The rotate right function can also be expressed using floor, subtraction, division, and powers. The XOR functions are used in triplicate so they define a relationship between the bits a_1 ^ b_1 ^ c_1 will be true if a_1 is different than b_1 and c_1 is false, but if c_1 is true than the result will be true if a_1 is the same as b_1.  This is about as far as I have gotten on cracking SHA256, but I assure you, it can be cracked. It will just take more time, and I am probably not the person to do it.

Only because if there were anything "up the sleeve" of the first N-bits of truncations of the cube roots of primes, number theory is what would lead to the description.  That is, if these truncations have properties at all.

The fact that the numbers are normal is good but does no exclude the possibility that finite truncations of such numbers have predictable properties.  The whole spirit of my post is to try to pose the relevant questions...which I think now are probably pointed right at these truncations, and whether or not they have any slippery properties under the transformations specified by SHA-2.

You are a boner.  This comment in no way adds to the conversation.  I hate you.

I was enjoying reading this discussion, even though I didn't 100% follow everything, and I think this is a really relevant and good discussion to be having in this community.  The fact that the constants are chosen systematically (roots of primes) rather than arbitrarily chosen, does give some confidence that there isn't some backdoor.

And then suddenly the thread turned hostile, with a really irrelevant post about stepping through an implementation of SHA-256 on a simulator?  That really had nothing to do with number theory which is the topic here.

Anyway, thanks for the good reading.  I learnt something.

This conversation has been wildly hilarious & informative. Thank You all.

Something to go on here: http://arxiv.org/abs/1308.0219



edit: for clarity, this is not about the current discussion, just a direct response to the OP.

I don't know why you think number theory can actually shine any light on this.
Taking the fractional part of a floating point number and multiplying it by 2**32 essentially gets you a nice garbage integer.
Because square/cube roots are believed to be normal numbers in base 2 http://mathworld.wolfram.com/NormalNumber.html (Their digit distribution certainly is random for the relevant part anyways), their decimal expansion is essentially a string of random (the important part) garbage. It has no interesting number theoretic properties left.
More importantly, the round constants are mixed through essentially bitwise operations, the number theory surrounding primes would have very little of interest to tell you, since it does not deal with the representations of numbers, while hash algorithms are essentially only bit twiddling, which mostly don't care about the numeric values used (only their binary representation).

Newbie question:: to the best of anyone's knowledge, do Bitcoin-Qt, other clients or Bitcoin related services use this Dual_EC_DRBG something?

Wow, razorfishsi, you should have taken more time to read this post as Altoidnerd was asking some valid questions and you might have missed some points and Altoidnerd you should not react so quickly and defensively. 
 Anyway, Altoidnerd, I think that often, the whole point of these maths/science things is asking what are the questions and not just what are the answers. If you can break these things down into what are the number theoretic questions that need to be answered then that is just as much of the work as providing the answer.
 Some of the most interesting/difficult mathematics is about providing the questions that need to be answered. So I don't think that what you're asking for is so straightforward.
 Hypotheses are just questions and Riemann, for example, is famous for asking a question, and not for providing an answer to it.

 
 

I get the idea you do not understand 'irony'

As regards the rest of the drivel you posted..., I can see from the fact that you 'cited' 'prickypidia' that your education is most possibly below BA level, anything about that level, you would have been educated in 'research skills' which in turn would have lead you to several papers on partial 'cracks' of the SHA256 algorithm.. upto about 25 bits.
There is also research on Hash prediction, something I myself have been interested in.

The fact that you do not  appear to be aware of these research areas (as you used neither to try and negate my post)  would lead me to believe you are more likely to be a fuckwit
who managed to pickup a couple of buzzwords

I get the feeling you are ignorant to number theory. The zeros do not just appear out of then air - they are deterministically manifest in the calculation steps prior to their appearance.

Do you fail to realize that SHA-1 was broken in a number of ways?  Tin foil hat my ASS.  It's mathematics - script kiddie isn't going to teach you how to do this sort of thing, so try this

http://link.springer.com/chapter/10.1007/11799313_9#page-1

Notice there how the big boy analysts don't whip out their computers, make a single calculation, and proceed to go online and play video games.  They could have said "well, ma, ain't no collisions yet, ain't n'er guna be none."  No, they actually quantified similarities between SHA-256 and SHA-1, like men with brains would do before crying on a forum that they understand something.

Secondly, while I'll admit this is off toipic, but just because you are a such an asshole, do you not suppose that I prefer to look at the algorithm as a mathematical object acting on sets rather than a particular programming language's implementation, holy shit, that's what I got my education in? Fucking math?

You are HIGH as a kite if you think looking at a terminal is going to illuminate more about this algorithm than a robust mathematical analysis of not only the statistics of the algorithm but the underlying number theory.  You are equally stoned, and on wacky shit, if you think what you did is an analysis of any sort.  

You might be too far behind, but if you want to be able to ever convince yourself the algorithm is not magic..far from it in fact, you can start by learning some new words

https://en.wikipedia.org/wiki/Prime_number
https://en.wikipedia.org/wiki/Rotation_(mathematics)

Please please just STOP...
Don't go copying bits of code and then start spouting about how you enjoy wearing a tinfoil hat, but that you  are not certain about all the details of  why you think you need one.


crack open the web version of xilinx tools then GO WALK the code, it's so simple even a complete MORON can follow it....
(yep I know you can use C++ or assembler, but following digital logic is WAY more expressive and clear)

an example:

hash & nonce (please note I pre-found the nonce thats why I know it is what it is)

here is the "midstate" and "data" for above number string not including  the nonce

And here is an example  of 'finding' the correct nonce



If you cannot figure out how to use the VHDL emulation tools, then you are not going to be able to figure out the  algorithm.
go watch the absolute magic of a value on a prior clock cycle, having absolutely no zero's at the top end... then wham.... They just appear...
Then step back each clock cycle and watch HOW they appear.. it's so simple.... but it is not... and that is the magic.

What does this give you?

well it gives you a complete bit level model of how it all works at each and every stage,  go play with it then go figure out answers to your very basic questions (by watching each stage at each CLK cycle you will SEE exactly what happens when you shift shit out of a bit container...)

As regards 'seeing' certain numbers..... have you ever noticed  that in base 2 you see a lot of '0' &  '1' or that  certain random numbers come up more often?

Unless you have a collaborative statistical analysis.. thenI'm afraid it is just your mind playing tricks.

I'm gonna stop and say right now I need to better visualize what this mixing of fractional parts of fractional powers of primes that follows is and how it plays out before I continue to blubber about this.  The discussion helped me clear my thoughts.  

Are any of the indexed, fractional prime powers from the length 8 list met with ones from 64 length list?  If so, the numbers {p - p^5/6| p is prime} would be relevant.  

no no.  wrong, ignore.

I don't think I lost you - you know what I'm asking.  What is the compliment then, of the set of pseudo random numbers?  Numbers in which some relationship is known between the digits?

I don't actually even think it is that simple.  If some rotational property of the prime's fractional powers' digits were known, it is another source of trouble...possibly.

Please keep in mind it is for science I am trying to attack the problem in a scholarly way.  I see not only the constants' digits themselves to be under scrutiny, but also the image of the function through which they are put.  

Here is a really simple example of a function f(h_i) which would be a bad function to follow the selection of the constants.

f(h_i) = (h_i)^2 + floor(p_i)

Why?  Because that function's image under the set {h0,h1,h2...} is the first 8 primes.

Obviously that is not even the type of function which follows.  It is only to illustrate the concept that the image is the questionable space, rather than the domain.

AFAIK the constants merely need to be psuedo-random values.  Using truly random values would provide security but wouldn't provide transparency (are those randoms really random).  The use of squares/cubes of primes is soley to be a "nothing up my sleeve number".  It could have been first 240 digits of Pi instead or a sequence of true random numbers based on radioactive decay or quantum RNG.

If the constants aren't randomly distributed it could undermine the security of the algorithm.

Thanks.  I will note here that you seem to be taking the stance that it is my opinion somehow that the constants are malicious, and that is not the case.

I am asking if it can be stated (and perhaps it cannot, or no one has done so...I have so far been unable to ponder it myself) what property, precisely, of real numbers we are clinging to here.  I will throw out my opinion in this regard - there probably IS at the very least a way to state in precise mathematical terms, what property of numbers we HOPE is in fact true.  Number theory always wins...that is not to say there is a weakness.  Asking the question - and what I am doing is saying "it can probably be asked more succinctly than simply stating the SHA-256," - asking if there is a property that must hold true is not to say "there is something up the sleeve of these choices."

You lost me here.


We are relying on the fact that the constants are psuedo random.  Any 49 truly random constants would be equally secure however the issue with that is if NIST provided you a list of 32 bit numbers they "randomly" generated would you trust them?  Essentially trust of SHA-2 would hinge on trust of NIST. If the constants are random then the algorithm is trusted and if they are not then it may hide a flaw.  Given that that randomness of the constants could never be proven it presents an interesting problem to public adoption.

The use of first 32 bits of square and cube root sequential primes is merely a method to introduce entropy into the algorithm.  We aren't relying on any specific property of square and cube roots merely that no exploitable relationship exists.  As for proving that, I doubt believe that is possible. 

I was thinking rather than wondering about magic numbers which caused the hard fork, or whatever, we could think for a moment about what exact number theory problem we are asking.  Is there a known open problem which, if shown to be true or false, would be relevant to the prime^1/2 and prime ^1/3 constants and their use in SHA-256?  What property of the digits in fractional powers of primes are we relying on to assure these are safe?  Just that the powers are irrational, or something else?

Well that is the point of "nothing up my sleeve numbers" it simplifies the crypto-analysis.  Rather than try to determine if there is any special relationship between 72 seemingly random constants, the use of sequential primes simplifies the question to is there any special relationship between the square and cube roots of a set of sequential primes that would undermine this algorithm.  

Granted both questions are well beyond my capabilities however the later question is a far simpler question if only in scope.    The quick detection of the flaw (intentional backoor) in another cryptographic system, by the international community provides a level of assurance.   SHA-2 has been extensively studied for the better part of a decade being the prominent hashing algorithm in a variety of applications.  Finding a flaw (intentional or otherwise) in one of the (if not the) most widely used hashing function is a huge deal for cryptographers.  Any lack of evidence to a special relationship certainly isn't due to a lack of trying.  When you compare the speed at which flaws were found in Dual_EC_DRBG and consider that is a far less know/used algorithm than SHA-2 it would have to be an amazingly well hidden backdoor.

I'm sitting here thinking about what the first 32 bits of a hex representation of prime(k)^(1/2) - floor(prime(k)^(1/2)), and again for prime(k)^(1/3), meaning kth prime, k = {1:64},  would mean in math words.  It is a question of divisibility or relative primeness?  Not sure if hex matters at all