SHA2-256 Linearized

[Willow Schlanger]

All,
I didn't receive any responses for my post last August, so I'm reposting
in case you missed it.

I successfully linearized SHA2-256 in an interative (instead of all-at-
once) way.

Source forge link for the implementation:
http://sourceforge.net/projects/linear-analysis/

Git hub link for the implementation:
http://github.com/wrschlanger/linear-analysis/

For a simple sample, here's a quick demo version:

https://github.com/wrschlanger/linear-analysis/raw/master/code/
seventh_updated.tar.gz

http://www.undocumented.info/home/willowschlanger/files/
seventh_updated.tar.gz

For the above, one has:

Expected file size: 17720679 bytes

Expected SHA2-512 value of file (broken into two lines):
fa526afde97876f6ab1a6bf3da3f76d7d7b89650d7449123d813eab569c5a54
22254795f2702f697afa8d9cd0d8be991d6c0ffe29ec89f31ae3118c77711c849

My paper is available here at present:

http://www.undocumented.info/home/willowschlanger/cla-v1.pdf

Use the above URL to obtain GIT instructions.

The paper is presently in very early draft form, but the implementation
is finished.

I have an arXiv account and would like to post my article despite it
being in an early draft form. Does anyone have experience with this, and
using a so-called endorser to do so?

Because both the paper and source code is public domain, feel free to
copy and/or post elsewhere.

Cheers,
Willow Schlanger

Update: This does not affect or relate to "breaking" SHA2, only
representing it for algorithm archiving purposes.

I should like over the long term to write a formal article, either for
computer science peer review (but it seems like you almost have to
already have been published to get published, or know somebody as even
ArXiV doesn't accept just any paper), or perhaps for Cryptolgia since
they will have a different kind of audience in mind and would be easier
to write an article for.

I'm probably going to look into article submission requirements.

Does anyone have experience with writing articles for peer review or even
computer or math-related magazines?

[Pubkeybreaker]

Post by Willow Schlanger
All,
I didn't receive any responses for my post last August, so I'm reposting
in case you missed it.
I successfully linearized SHA2-256 in an interative (instead of all-at-
once) way.

<snip>

complete crap

[Peter Pearson]

Post by Willow Schlanger
All,
I didn't receive any responses for my post last August, so I'm reposting
in case you missed it.

[snip]

Post by Willow Schlanger
http://www.undocumented.info/home/willowschlanger/cla-v1.pdf

A word of advice: before you ask the reader to invest time and energy in
learning your terminology and the internal details of your algorithms,
you need to convince the reader that you have accomplished something
worth listening to. Reading the above-named PDF file, I am confronted
with a "Definitions" section immediately after reading an Abstract
that seems to explain little more than that you can perform something
resembling SHA256 by performing (and this is no surprise) linear
steps interspersed with nonlinear steps using a "relatively compact"
20,000-by-20,000 matrix of 33-bit integers.


[snip]

Post by Willow Schlanger
Update: This does not affect or relate to "breaking" SHA2, only
representing it for algorithm archiving purposes.

Is this the important part of your work, finding a way to express an
algorithm in a representation that will still be intelligible after the
world has wandered so far from the present that C and Python and
pseudocode are no longer intelligible, but we still use SHA256?

[Willow Schlanger]

Hi Peter,
Thanks for writing back. My responses are below.
[snip]

Post by Peter Pearson
A word of advice: before you ask the reader to invest time and energy in
learning your terminology and the internal details of your algorithms,
you need to convince the reader that you have accomplished something
worth listening to. Reading the above-named PDF file, I am confronted
with a "Definitions" section immediately after reading an Abstract that
seems to explain little more than that you can perform something
resembling SHA256 by performing (and this is no surprise) linear steps
interspersed with nonlinear steps using a "relatively compact"
20,000-by-20,000 matrix of 33-bit integers.

Part I.

In order to become convinced that I have accomplished something worth
listening to, please follow these steps on a Linux machine:

1. $ wget http://www.undocumented.info/
home/willowschlanger/files/seventh_updated.tar.gz
2. (The previous command should be all one line).
3. $ tar xzvf seventh_updated.tar.gz
4. (the previous step will produce the seventh_updated/ directory,
along with several files including compute1.cpp and sha2_256_out.txt,
a very large text file. the text file in question is almost 4 gigabytes
and is a linear matrix of non-negative integers, all in the 0 through
2^(33)-1 range, inclusive, where ^ denotes 'to the power of').
5. $ cd seventh_updated
6. $ g++ -O -o compute1.out compute1.cpp
7. $ ./compute1.out
8. The program in question will, in a fully linear but iterative way,
compute the SHA2-512 value of "hellosir", shjowing the computed "Result"
as output.
9. A 19328x19328-sized linear matrix of coefficients was used to perform
this task.
10. Although this is discouraged, you can view the actual base-16
coefficient values in the text file, if you like.
11. Next, examine compute1.cpp to get a feel for what you just
accomplished.

In essence, the most important part of compute1.cpp is this function,
which has had only the important parts retained for sake of discussion:

Part II.

bool acceptRow(int rowNumber, uint64_t row[])
{
int i = 0;

int ii = 0;

for(i = rowNumber + 1; i < numT; ++i)
{
if(row[i] != 0)
{
std::cout << "\nFail case BB" << std::endl;

std::cout << "Fail, row " << (int) rowNumber << std::endl;

return false;
}
}

if(row[rowNumber] != get_sign_constant())
{
std::cout << "\nFail case B" << std::endl;

std::cout << "Fail, row " << (int) rowNumber << " " <<
row[rowNumber] << std::endl;

return false;
}

ii = i;

struct {
uint64_t x : 33;
} value;

value.x = 0;

for(i = 0; i < numT + numX + numC; ++i)
{
value.x += row[i] * values[i];
}

values[rowNumber] = value.x / ((1uLL << 16) << 16);

known[rowNumber] = true;

return true;
}

Part III.

You provided a very well thought out observation that it seems from my PDF
that I claim, I have succeeded in:

little more than that you can perform something
resembling SHA256 by performing (and this is no surprise) linear steps
interspersed with nonlinear steps using a "relatively compact"
20,000-by-20,000 matrix of 33-bit integers."

Part IV. Response to Part III.

Your observation is very definitely accurate; in fact, though, source
code was also provided to automatically convert algorithms described to a
computer using a programatically-generated Abstract Syntax Tree
representation, which basically represents a functional description of an
algorithm such as SHA2 or, crucially, any other algorithm meeting certain
criteria, using C++ objects in memory in a functional way; an automated
process of linearizing that into a fully linear matrix with a "non-
linear" operation being required to use the matrix of coefficients to
achieve the same effect as the original algorithm, was also developed.

That is to say, source code not only for the successful use of the matrix
produced for the SHA2-256 case, but also to produce the matrix in
question, and the ability to do so for any use-specified algorithm that
meets certain criteria, was also provided. Please see the original post
for the full source code links on sourceforge and github.

part V. Additional details.

Actually, the rather minor advances in computer theory that was made are:

1. The identification of a compression argument about why a fully linear
matrix couldn't otherwise be used;

2. The precise nonlinear constraint that is required that has to be
pushed to the end user, specifically that one has a word-sized state
vector whose allowed input es can be only 0 or 1, i.e. s^(2) = s must be
satisfied for each word-sized, non-negative integer, vector element.

3. Specifically, no true nonlinear "ops" need to be performed, one need
only perform a series of linear computations, one row at a time,
basically dot products, i.e. the computation of an output column vector
element's value in the way one normally does when performing matrix
multiplication. If each non-negative integer result is truncated to w-
bits (w=33 is used in the application example), then each resulting
column vector's element value will be either 0 or 2^(w-1), precisely. To
perform the computation, one made a 'guess' about exactly one new state
vector element value, i.e. 0 or 1, and if the guess was exactly wrong, a
value of 2^(w-1) would be obtained; one can then make the opposite guess.

4. In an interative, i.e. step-by-step process, then, a new column vector
of w-bit sized, non-negative integer column vector values can be computed
that will be all 0s when finished; at that time, the correct guesses for
the input state vector will have been obtained and the element positions
corresponding to the output values can be looked up.

[snip]

Post by Peter Pearson
Is this the important part of your work, finding a way to express an
algorithm in a representation that will still be intelligible after the
world has wandered so far from the present that C and Python and
pseudocode are no longer intelligible, but we still use SHA256?

Actually, that is the only part of the work, although it is remotely
exciting that a linear system of equations can represent both XOR and AND
subject to only the nonlinear constraint that s^(2) = s.

I want to thank you for taking the time to write back! I have an interest
in writing a computer theory paper to describe the above, with the hopes
of either passing peer review or, if I choose, instead I'd like to send
it to cryptolgia or a similar magazine or journal.

Actually, the concepts demonstrated might not sound terrible novel, but
the concept of using "delta-state vectors" is a new way of thinking that
could be come useful again when studying quantum physics, where systems
are being studied with some amount of purposeful, initial macroscopic-
state ignorance.

Thus, getting some kind of application of the underlying concepts out
into the world would be quite useful to a lot of people working on theory.

Finally, thousands of years into the future, python etc. really will be
defunct and being able to record an algorithm in a way anybody who knows
linear algebra can understand, as long as it's a "stateless" algorithm
whose output depends only on the input but which retains no memory of its
prior use (hey, we can even do arbitrary look-up tables, not just
algorithms like SHA2) is fairly exciting.

Cheers!

Willow Schlanger

The following applies to seventh_updated.tar.gz which can also be
obtained from GIT, sourceforge, and my two websites:

Expected file size: 17720679 bytes

Expected SHA2-512 value of file (broken into two lines):
fa526afde97876f6ab1a6bf3da3f76d7d7b89650d7449123d813eab569c5a54
22254795f2702f697afa8d9cd0d8be991d6c0ffe29ec89f31ae3118c77711c849

[Pubkeybreaker]

This post might be inappropriate. Click to display it.

[Richard Outerbridge]

Post by Pubkeybreaker

Post by Willow Schlanger
Hi Peter,
Thanks for writing back. My responses are below.
[snip]

<snip>
https://www.schneier.com/crypto-gram/archives/1998/1015.html#cipherdesign
Read it. Act on it.

Always a classic, though Schnier himself, like the rest of us, after
all, is a slight bit of a charlatan.

Bruce, of anyone I know bearing witness to what passes for truth, still
doesn't mean we ring true like a $3.00 coin.
__outer