
Date: Wed, 23 Sep 2015 19:12:21 +0300 From: Aleksey Cherepanov <lyosha@...nwall.com> To: johndev@...ts.openwall.com Subject: Re: Reverse steps for single round sha(sha1, 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 sha512, 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/([ah]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