[Cryptography] SHA-256 decrypted (8 rounds)
McDair
mcdair at protonmail.com
Sat Nov 11 09:59:28 EST 2023
Op zaterdag 11 november 2023 om 00:59 schreef Jon Callas <jon at callas.org>:
> McDair,
>
> This is nice work, thanks for sharing it with us. No harm in using VB; it's a language.
>
> Similar to what Michael Kjörling said, though, are you claiming anything with it beyond eight rounds of cryptanalysis.
>
> Hash functions of this sort use an internal block cipher, and then a chaining mechanism to combine iterations of the cipher in to the actual hash function. SHA2 in all its forms uses Merkle-Damgård chaining which has issues, and so modern hash functions use different mechanisms.
>
> However, that's not really relevant here. It's natural and expected that any sort of function will have effective cryptanalysis for some number of rounds and then no more. This is more or less what the colloquial term "avalanche" means -- that uncertainties in tracing paths collapse after a certain number of rounds.
>
> In 2003, Gilbert and Handshuh wrote, "Security Analysis of SHA-256 and Sisters" https://link.springer.com/content/pdf/10.1007/978-3-540-24654-1_13.pdf and they found a 9-round differential and a separate (much better) one for 4 rounds. Note there's a total of 80 rounds.
>
>
> After Wang's attacks on everything in 2004, there was another 2008 paper, "Collisions and other Non-Random Properties for Step-Reduced SHA-256" by Indesteege, Mendel, Preneel, and Rechberger, https://eprint.iacr.org/2008/131.pdf where they find a 23-round collision with effort 2^18, and a 24-round collision with effort 2^28.5. (Note their "steps" appear to be the same thing as G&H's "rounds" and are cited in that paper as steps.)
>
>
> Presently, we generally consider SHA-2 to be a known quantity. I'll admit that all of the brain cycles I spent on it a long time ago have suffered from bitrot and I had to go skim papers to catch up. So please don't take it as an insult that I'm asking what results are, I just want the TL;DR.
>
> It seems to me that you've bettered some of the initial cryptanalysis by getting to 8 rounds with certainty, but what does that really mean? Can you extend that out, given that you have a good differential? Can that be turned into reduced round collisions? Pre-image attacks?
>
> Pre-image attacks would be very interesting because that not only affects signatures, but would challenge the way that Bitcoin doubles SHA-256. I'm not sure what you have, though. Moreover, eight rounds out of eighty is good news for the hash function, usually, because there's 72 rounds to go.
>
> I don't even know if you're presenting this as a weakness or a strength. Either way, it's nice to see, I'm just confused.
>
> Jon
>
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> https://www.metzdowd.com/mailman/listinfo/cryptography
Dear Jon,
Thank you for your insight and references!
To give you the TL;DR:
The previous code is indeed a step(/round)-reduced preimage 'attack'.
For 8 rounds it extracts the exact input message from the resulting hash.
As for your question whether this can be extended out:
Hereunder is similar code to extract 'a' valid input message (yielding to the original output hash), for the full SHA-256 64 rounds (SHA-512 has 80 rounds).
Please note this code is a stripped down version, whereby all 64 words (used by each round) are to be provided manually.
Meaning the additional bit, message length and 48 extension words contained within these 64 words are not being validated.
Needless to say this is also an essential part of SHA-2 security, but maybe a story for another day.
Example for those who can not run the below code:
64 input words with values
1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32,
33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48,
49, 50, 51, 52, 53, 54, 55, 56,
57, 58, 59, 60, 61, 62, 63, 64
hashes to f2b8059b75669384a376fb2e2b166d4d9dbdac22f76f48bb56f407441f97bbff using the SHA-256 main compression function.
64 input words with values
812800583,3127260494,2517362691,2619288377,1125487444,3641750224,3622967028,3720334552,
3616249441,1180008241,541459887,2013668387,814151095,2635198174,3804182261,2012702787,
2794272154,1064413761,952618804,2888261098,1917585984,3366689923,691059316,2647954690,
2658651294,1513670244,501964396,1356129324,754841364,1656483856,185435081,2914682849,
638731123,553565003,3951076597,4243191865,18727574,260870298,2861854734,1425051026,
3181215776,3733410742,30181410,3712398766,3441735417,2946519213,2652390704,2409732567,
1928825890,3329000628,3707245419,1910506924,4286392077,1528179131,1438100643,1365357685,
4199864568,571182368,9437012,1887239697,2237734381,1669077494,2215961480,1343804553
also hashes to f2b8059b75669384a376fb2e2b166d4d9dbdac22f76f48bb56f407441f97bbff using the SHA-256 main compression function.
As to how it works: I can't explain it better than providing the commented code.
PS: I'm a big fan of Bitcoin!
Sincerely,
McDair
Option Explicit On
Option Strict On
Module Main
Sub Main()
Dim sha As New Sha256
Dim wordsOriginal As UInt32() = New UInt32() {
1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32,
33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48,
49, 50, 51, 52, 53, 54, 55, 56,
57, 58, 59, 60, 61, 62, 63, 64
}
Dim hash = sha.Encrypt(sha.initHash, wordsOriginal, Nothing) ' get hash of 'real' input message (64 rounds in this version)
Dim wordsFound = sha.Decrypt(hash, Nothing, Nothing) ' find preimage (64 rounds in this version)
Dim hashFound = sha.Encrypt(sha.initHash, wordsFound, Nothing) ' check if hash of found message is the same as 'real' input message hash
If hashFound.SequenceEqual(hash) Then
MsgBox("Same resulting hash. " & vbCrLf &
hash(0).ToString("x8") & hash(1).ToString("x8") & hash(2).ToString("x8") & hash(3).ToString("x8") &
hash(4).ToString("x8") & hash(5).ToString("x8") & hash(6).ToString("x8") & hash(7).ToString("x8"))
Else
MsgBox("Different resulting hash.")
End If
End Sub
End Module
Option Explicit On
Option Strict On
Public Class Sha256
Private Const forceOperationInt64 As Int64 = 0
Private Const forceOperationUInt64 As UInt64 = 0
' for debugging
Private ReadOnly rounds As Integer = 64
' algorithm constants
Private ReadOnly k As UInt32() = New UInt32() {
&H428A2F98UI, &H71374491UI, &HB5C0FBCFUI, &HE9B5DBA5UI, &H3956C25BUI, &H59F111F1UI, &H923F82A4UI, &HAB1C5ED5UI,
&HD807AA98UI, &H12835B01UI, &H243185BEUI, &H550C7DC3UI, &H72BE5D74UI, &H80DEB1FEUI, &H9BDC06A7UI, &HC19BF174UI,
&HE49B69C1UI, &HEFBE4786UI, &HFC19DC6UI, &H240CA1CCUI, &H2DE92C6FUI, &H4A7484AAUI, &H5CB0A9DCUI, &H76F988DAUI,
&H983E5152UI, &HA831C66DUI, &HB00327C8UI, &HBF597FC7UI, &HC6E00BF3UI, &HD5A79147UI, &H6CA6351UI, &H14292967UI,
&H27B70A85UI, &H2E1B2138UI, &H4D2C6DFCUI, &H53380D13UI, &H650A7354UI, &H766A0ABBUI, &H81C2C92EUI, &H92722C85UI,
&HA2BFE8A1UI, &HA81A664BUI, &HC24B8B70UI, &HC76C51A3UI, &HD192E819UI, &HD6990624UI, &HF40E3585UI, &H106AA070UI,
&H19A4C116UI, &H1E376C08UI, &H2748774CUI, &H34B0BCB5UI, &H391C0CB3UI, &H4ED8AA4AUI, &H5B9CCA4FUI, &H682E6FF3UI,
&H748F82EEUI, &H78A5636FUI, &H84C87814UI, &H8CC70208UI, &H90BEFFFAUI, &HA4506CEBUI, &HBEF9A3F7UI, &HC67178F2UI
}
Friend ReadOnly initHash As UInt32() = New UInt32() {
&H6A09E667UI, &HBB67AE85UI, &H3C6EF372UI, &HA54FF53AUI, &H510E527FUI, &H9B05688CUI, &H1F83D9ABUI, &H5BE0CD19UI
}
Private Function RightRotate(value As UInt32, bits As Byte) As UInt32
Return (value >> bits) Or (value << (32 - bits))
End Function
Friend Function Encrypt(hash As UInt32(),
words As UInt32(),
ByRef debugVariables As UInt32(,)) As UInt32()
Dim a, b, c, d, e, f, g, h As UInt32
Dim s1_ch_k_h_w As UInt64
Dim round As Integer
Dim resultHash(7) As UInt32
' for debugging
Dim variables((Me.rounds + 1) - 1, 7) As UInt32
' initialize working variables to current hash value
a = hash(0)
b = hash(1)
c = hash(2)
d = hash(3)
e = hash(4)
f = hash(5)
g = hash(6)
h = hash(7)
' for debugging
variables(0, 0) = a
variables(0, 1) = b
variables(0, 2) = c
variables(0, 3) = d
variables(0, 4) = e
variables(0, 5) = f
variables(0, 6) = g
variables(0, 7) = h
' compression function main loop
For round = 0 To Me.rounds - 1
s1_ch_k_h_w = Sha256.forceOperationUInt64 +
(Me.RightRotate(e, 6) Xor Me.RightRotate(e, 11) Xor Me.RightRotate(e, 25)) +
((e And f) Xor ((Not e) And g)) +
Me.k(round) +
h +
words(round)
h = g
g = f
f = e
e = CType((d + s1_ch_k_h_w) And UInt32.MaxValue, UInt32)
d = c
c = b
b = a
a = CType((
s1_ch_k_h_w +
(Me.RightRotate(b, 2) Xor Me.RightRotate(b, 13) Xor Me.RightRotate(b, 22)) +
((b And c) Xor (b And d) Xor (c And d))
) And UInt32.MaxValue, UInt32)
' for debugging
variables(round + 1, 0) = a
variables(round + 1, 1) = b
variables(round + 1, 2) = c
variables(round + 1, 3) = d
variables(round + 1, 4) = e
variables(round + 1, 5) = f
variables(round + 1, 6) = g
variables(round + 1, 7) = h
Next
' for debugging
debugVariables = variables
resultHash(0) = CType((Sha256.forceOperationUInt64 + hash(0) + a) And UInt32.MaxValue, UInt32)
resultHash(1) = CType((Sha256.forceOperationUInt64 + hash(1) + b) And UInt32.MaxValue, UInt32)
resultHash(2) = CType((Sha256.forceOperationUInt64 + hash(2) + c) And UInt32.MaxValue, UInt32)
resultHash(3) = CType((Sha256.forceOperationUInt64 + hash(3) + d) And UInt32.MaxValue, UInt32)
resultHash(4) = CType((Sha256.forceOperationUInt64 + hash(4) + e) And UInt32.MaxValue, UInt32)
resultHash(5) = CType((Sha256.forceOperationUInt64 + hash(5) + f) And UInt32.MaxValue, UInt32)
resultHash(6) = CType((Sha256.forceOperationUInt64 + hash(6) + g) And UInt32.MaxValue, UInt32)
resultHash(7) = CType((Sha256.forceOperationUInt64 + hash(7) + h) And UInt32.MaxValue, UInt32)
Return resultHash
End Function
Private Function GetVariablesLastRound(refHash As UInt32(), hash As UInt32()) As UInt32()
Dim variables(7) As UInt32
variables(0) = CType((Sha256.forceOperationInt64 + refHash(0) - hash(0)) And UInt32.MaxValue, UInt32)
variables(1) = CType((Sha256.forceOperationInt64 + refHash(1) - hash(1)) And UInt32.MaxValue, UInt32)
variables(2) = CType((Sha256.forceOperationInt64 + refHash(2) - hash(2)) And UInt32.MaxValue, UInt32)
variables(3) = CType((Sha256.forceOperationInt64 + refHash(3) - hash(3)) And UInt32.MaxValue, UInt32)
variables(4) = CType((Sha256.forceOperationInt64 + refHash(4) - hash(4)) And UInt32.MaxValue, UInt32)
variables(5) = CType((Sha256.forceOperationInt64 + refHash(5) - hash(5)) And UInt32.MaxValue, UInt32)
variables(6) = CType((Sha256.forceOperationInt64 + refHash(6) - hash(6)) And UInt32.MaxValue, UInt32)
variables(7) = CType((Sha256.forceOperationInt64 + refHash(7) - hash(7)) And UInt32.MaxValue, UInt32)
Return variables
End Function
Private Sub OutputResult(resultVariables As UInt32(,), resultWords As UInt32(),
refVariables As UInt32(,), refWords As UInt32(),
actualVariables As UInt32(,), actualWords As UInt32())
Dim round As Integer
Dim variable As Integer
For round = Me.rounds To 0 Step -1
Debug.Write("------------------------- variables n - " & round)
If round < Me.rounds Then
Debug.WriteLine(" | w = " & actualWords(round).ToString.PadRight(10) & " | w found = " & resultWords(round))
Else
Debug.WriteLine("")
End If
For variable = 0 To 7
Debug.WriteLine(actualVariables(round, variable).ToString.PadRight(10) & " | " &
refVariables(round, variable).ToString.PadRight(10) & " | " &
resultVariables(round, variable).ToString.PadRight(10)
)
Next
Next
End Sub
Friend Function Decrypt(hash() As UInt32, debugWords()() As UInt32, debugVariables()(,) As UInt32) As UInt32()
Dim refWords(Me.rounds - 1) As UInt32
Dim refVariables(,) As UInt32
Dim variablesLastRound As UInt32()
Dim resultVariables As UInt32(,)
Dim resultWords As UInt32()
Dim round As Integer
Dim a_ref, b_ref, c_ref, d_ref, e_ref, f_ref, g_ref, h_ref As UInt32
Dim a_res, b_res, c_res, d_res, e_res, f_res, g_res, h_res As UInt32
Dim s0_maj_ref As Int64
Dim s0_maj_res As Int64
Dim diff_s0_maj As Int64
Dim diff_d As Int64
Dim word As UInt32
variablesLastRound = Me.GetVariablesLastRound(hash, Me.initHash)
' start with empty reference words
' get reference variables for words passed (words passed are initially empty)
' (we don't use the resulting hash)
refVariables = Nothing
Me.Encrypt(Me.initHash, refWords, refVariables)
resultVariables = Nothing
resultWords = Nothing
Me.Decrypt(variablesLastRound, refVariables, resultVariables, resultWords)
If debugVariables IsNot Nothing And debugWords IsNot Nothing Then
Me.OutputResult(resultVariables, resultWords, refVariables, refWords, debugVariables(0), debugWords(0))
End If
' resulting round 0 variables e, f, g, h should match actual round 0 variables (initial hash)
' we can now check whether resulting w1 is correct:
' 1) resulting w1 is incorrect when resulting d0 doesn't match actual d0 (initial hash) because:
' e1 = d0 + fx(e0, f0, g0) + k1 + h0 + w1
' --> h0 resolves to correct (initial hash) value, so we can leave h0 out of the equation
' --> e0, f0, g0 resolve to correct (initial hash) values, so we can leave fx(e0, f0, g0) out of the equation
' --> d0 doesn't resolve to correct (initial hash) value, so we have to take into account the difference
' of resulting d0 and actual d0 to adjust resulting w1
' 2) resulting w1 is incorrect when resulting fx(a0, b0, c0) doesn't match actual fx(a0, b0, c0) because:
' a1 = fx(e0, f0, g0) + k1 + h0 + w1 + fx(a0, b0, c0)
' --> h0 resolves to correct (initial hash) value, so we can leave h0 out of the equation
' --> e0, f0, g0 resolve to correct (initial hash) values, so we can leave fx(e0, f0, g0) out of the equation
' --> fx(a0, b0, c0) doesn't resolve to correct value, so we have to take into account the difference
' of resulting fx(a0, b0, c0) and actual fx(a0, b0, c0) to adjust resulting w1
' adjust reference words (and reference variables as a result)
For round = 0 To Me.rounds - 1 - 4
a_ref = refVariables(round, 0)
b_ref = refVariables(round, 1)
c_ref = refVariables(round, 2)
d_ref = refVariables(round, 3)
e_ref = refVariables(round, 4)
f_ref = refVariables(round, 5)
g_ref = refVariables(round, 6)
h_ref = refVariables(round, 7)
a_res = resultVariables(round, 0)
b_res = resultVariables(round, 1)
c_res = resultVariables(round, 2)
d_res = resultVariables(round, 3)
e_res = resultVariables(round, 4)
f_res = resultVariables(round, 5)
g_res = resultVariables(round, 6)
h_res = resultVariables(round, 7)
' difference sum(s0, maj)
s0_maj_ref = Sha256.forceOperationInt64 +
(Me.RightRotate(a_ref, 2) Xor Me.RightRotate(a_ref, 13) Xor Me.RightRotate(a_ref, 22)) +
((a_ref And b_ref) Xor (a_ref And c_ref) Xor (b_ref And c_ref))
s0_maj_res = Sha256.forceOperationInt64 +
(Me.RightRotate(a_res, 2) Xor Me.RightRotate(a_res, 13) Xor Me.RightRotate(a_res, 22)) +
((a_res And b_res) Xor (a_res And c_res) Xor (b_res And c_res))
diff_s0_maj = s0_maj_res - s0_maj_ref
' difference d
diff_d = Sha256.forceOperationInt64 + d_res - d_ref
' word found
word = CType((diff_s0_maj - diff_d) And UInt32.MaxValue, UInt32)
refWords(round) = word
'refWords(round) = CType((Sha256.forceOperationUInt64 + refWords(round) + word) And UInt32.MaxValue, UInt32)
' get reference variables for words passed
' (we don't use the resulting hash)
refVariables = Nothing
Me.Encrypt(Me.initHash, refWords, refVariables)
resultVariables = Nothing
resultWords = Nothing
Me.Decrypt(variablesLastRound, refVariables, resultVariables, resultWords)
If debugVariables IsNot Nothing And debugWords IsNot Nothing Then
Me.OutputResult(resultVariables, resultWords, refVariables, refWords, debugVariables(0), debugWords(0))
End If
Next
Return resultWords
End Function
Private Sub Decrypt(variablesLastRound As UInt32(), refVariables As UInt32(,),
ByRef resultVariables As UInt32(,),
ByRef resultWords As UInt32())
Dim a, b, c, d, e, f, g, h As UInt32
Dim s1_ch_k_h_w_prev As Int64
Dim h_w_prev As Int64
Dim w_prev As Int64
Dim round As Integer
Dim variables(Me.rounds, 7) As UInt32
Dim words(Me.rounds - 1) As UInt32
a = variablesLastRound(0)
b = variablesLastRound(1)
c = variablesLastRound(2)
d = variablesLastRound(3)
e = variablesLastRound(4)
f = variablesLastRound(5)
g = variablesLastRound(6)
h = variablesLastRound(7)
variables(Me.rounds, 0) = a
variables(Me.rounds, 1) = b
variables(Me.rounds, 2) = c
variables(Me.rounds, 3) = d
variables(Me.rounds, 4) = e
variables(Me.rounds, 5) = f
variables(Me.rounds, 6) = g
variables(Me.rounds, 7) = h
For round = Me.rounds - 1 To 0 Step -1
' determine previous d
' --------------------
' current e = previous d + sum(previous s1, ch, k, h, w)
' so previous d = current e - sum(previous s1, ch, k, h, w)
' so we have to know sum(previous s1, ch, k, h, w) in order to determine previous d
' current a = sum(previous s1, ch, k, h, w) + sum(previous s0, maj)
' so sum(previous s1, ch, k, h, w) = current a - sum(previous s0, maj)
' we know current a, and we can calculate sum(previous s0, maj)
s1_ch_k_h_w_prev = a -
(Sha256.forceOperationInt64 +
(Me.RightRotate(b, 2) Xor Me.RightRotate(b, 13) Xor Me.RightRotate(b, 22)) +
((b And c) Xor (b And d) Xor (c And d))
)
' now we know sum(previous s1, ch, k, h, w) and so we can determine previous d
' determine previous h
' --------------------
' obviously there is no direct way to determine previous h,
' but we can however calculate the sum of previous h and w
' we already know the value of sum(previous s1, ch, k, h, w), which we will call x here
' x = previous s1 + previous ch + previous k + previous h + previous w
' so previous h + previous w = x - previous s1 - previous ch - previous k
' we can calculate previous s1 and previous ch and we know previous k
h_w_prev = s1_ch_k_h_w_prev -
(Me.RightRotate(f, 6) Xor Me.RightRotate(f, 11) Xor Me.RightRotate(f, 25)) -
((f And g) Xor ((Not f) And h)) -
Me.k(round)
' now we know the sum of previous h and w
' when we substract reference variable (previous) h from this sum,
' we get an intermediate value for previous w
' (and as a result we can calculate the intermediate value for previous h)
' ultimately, when we keep substracting reference variable (previous) h in each round,
' initial variables found for at least e, f, g, and h would equal initial reference variables
' from there on, we will have to adjust reference variables (reference words)
' in order for all variables found to comply with reference variables
w_prev = h_w_prev - refVariables(round, 7)
a = b
b = c
c = d
d = CType((e - s1_ch_k_h_w_prev) And UInt32.MaxValue, UInt32)
e = f
f = g
g = h
h = CType(h_w_prev - w_prev, UInt32)
variables(round, 0) = a
variables(round, 1) = b
variables(round, 2) = c
variables(round, 3) = d
variables(round, 4) = e
variables(round, 5) = f
variables(round, 6) = g
variables(round, 7) = h
words(round) = CType(w_prev And UInt32.MaxValue, UInt32)
Next
resultVariables = variables
resultWords = words
End Sub
End Class
More information about the cryptography
mailing list