[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20150923161221.GA11659@openwall.com>
Date: Wed, 23 Sep 2015 19:12:21 +0300
From: Aleksey Cherepanov <lyosha@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: Reverse steps for single round sha(sha-1,
sha256/384/512)
On Wed, Apr 11, 2012 at 04:17:56PM +0800, myrice wrote:
> It is possible to do some steps reverse in single round hash, for example,
> in sha-512, message is less than 1024 bits. I am currently working on
> XSHA512 for Mac Lion OS. The maximum length of password is 107(107*8 <
> 1024). Here is my initial idea of reverse.
> Currently, we first compare first 64 bit of hashes. The code likes(Please
> refer to cuda/xsha512.cu for more details):
>
>
> initial H[0..7]; a..h = H[0..7]* for* i *from* 0 to 79
> t1 := ...
> t2 := ...
> h := g
> g := f
> f := e
> e := d + t1
> d := c
> c := b
> b := a
> a := t1 + t2
> H[0] += a
>
> For cipher text which is H`[0] append H`[1] append .... H`[7];
> 1) H`[0..7] -= H[0..7], we get a80, b80, c80...h80. These means a, b...h in
> (i=79)
> 2) Please see code above, the b80 = a79, c80 = b79, d80 = c79,
> e80=d79+t1_80. However, we don't know t1_80, so stop here.
> 3) And b79 = a78, c79 = b78, d79 = c78 ... b78 = a77, c78 = b77, d78 = c77
> 4) Focus on d80, d80 = c79 = b78 = a77 = t1_77+t2_77. We don't know t1_77
> and t2_77
>
> For now, we can compute to 77th iteration and compare a77 with d80.
>
> Any ideas about it? I think t1 and t2 are main reasons for us to reverse
> more steps.
Recently Solar mentioned a macro with reverse of 3 rounds of SHA2, but
7 rounds can be reversed.
Below there is generic backward step for SHA2 as if it is last, next
can be obtained just decreasing "indexes", e.g. with the following
perl filter: perl -pe 's/([a-h]|i = )(\d+)/$1 . ($2 - 1)/ge'
i = 63
g63 = h64
f63 = g64
e63 = f64
c63 = d64
b63 = c64
a63 = b64
s0 = ror(b64, 2) ^ ror(b64, 13) ^ ror(b64, 22)
maj = (b64 & c64) ^ (b64 & d64) ^ (c64 & d64)
t2 = s0 + maj
s1 = ror(f64, 6) ^ ror(f64, 11) ^ ror(f64, 25)
ch = (f64 & g64) ^ (~f64 & h64)
d63 = e64 - (a64 - t2)
h63 = a64 - t2 - (s1 + ch + k[i] + w[i])
Below there are my formulas with t1 and t2 substituted and without
parts that depend onto unknown data.
i = 63
g63 = h64
f63 = g64
e63 = f64
c63 = d64
b63 = c64
a63 = b64
s0 = ror(b64, 2) ^ ror(b64, 13) ^ ror(b64, 22)
maj = (b64 & c64) ^ (b64 & d64) ^ (c64 & d64)
d63 = e64 - (a64 - (s0 + maj))
i = 62
f62 = g63
e62 = f63
c62 = d63
b62 = c63
a62 = b63
s0 = ror(b63, 2) ^ ror(b63, 13) ^ ror(b63, 22)
maj = (b63 & c63) ^ (b63 & d63) ^ (c63 & d63)
d62 = e63 - (a63 - (s0 + maj))
i = 61
e61 = f62
c61 = d62
b61 = c62
a61 = b62
s0 = ror(b62, 2) ^ ror(b62, 13) ^ ror(b62, 22)
maj = (b62 & c62) ^ (b62 & d62) ^ (c62 & d62)
d61 = e62 - (a62 - (s0 + maj))
i = 60
c60 = d61
b60 = c61
a60 = b61
s0 = ror(b61, 2) ^ ror(b61, 13) ^ ror(b61, 22)
maj = (b61 & c61) ^ (b61 & d61) ^ (c61 & d61)
d60 = e61 - (a61 - (s0 + maj))
i = 59
c59 = d60
b59 = c60
a59 = b60
i = 58
b58 = c59
a58 = b59
i = 57
a57 = b58
Thanks!
--
Regards,
Aleksey Cherepanov
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
