※ ALHA에서 사용되는 바이트와 워드 단위는 각각 무부호의 8비트(unsigned 8-bit), 무부호의 32비트(unsigned 32-bit)임. 즉, 바이트 A=(a7,a6,...,a0)는 정수 a727 + a626 + ... + a020으로, 워드 A=(a31,a30,...,a0)는 정수 a31231 + a30230 + ... + a020으로 간주
※ 모든 바이트열과 워드열은 빅엔디안 형식으로 표기
※ 바이트열 B=(B[0],B[1],B[2],B[3],...)과 워드열 W=(W[0],W[1],W[2],...)은 다음과 같이 상호 변환됨:
MD4, SHA series 등의 해쉬함수를 공격하기 위해서는 대개 한 비트씩 값을 바꾸면서 그 출력값의 변화를 보는 방법을 사용한다. 이를 흔히 차분공격(differential attack)이라고 한다. Wang의 선구적인 연구로 인해 이에 대한 굉장히 세련된 방법이 존재하지만 그 방법을 필자가 제대로 이해하고 있지 못하다. 따라서 필자는 독자적인 방법으로 이 문제에 접근하려고 한다.
우선 위 문제는 실제 SHA-0의 알고리즘과 2가지 차이점이 있다.
1) 블록단위 메시지 처리 단계2-2에서 원래의 알고리즘이라면 xor 확장조건이 다음과 같다.
Wi = Wi-3 xor Wi-8 xor Wi-14 xor Wi-16, 16 ≤ i < 80
2) 블록단위 메시지 처리 단계2-4에서 원래의 알고리즘이라면 T는 다음과 같이 정의된다.
(A<<<5) ⊞ F ⊞ E ⊞ K ⊞ Wi[j]
문득 이런 생각이 들었다. 실제 SHA-0와 알고리즘이 굉장히 유사한데, 실제 SHA-0에서의 충돌쌍을 통해 위 문제의 충돌쌍을 구할 수 있지 않을까? 다음은 SHA-0의 충돌쌍의 예시이다.
출처 : 이미지 클릭
이제 그 방법이 정말 가능한지, 구체적으로 문제를 어떻게 풀어야 하는지 이 포스팅에서 보이려고 한다.(결론부터 말하면 위 충돌쌍의 예시로 충돌쌍을 찾는 것은 불가능하다. 이 포스팅은 어떤 시행착오를 거쳐서 올바른 알고리즘을 찾았는지 보여주기 위한 목적이다.) 우선 실제 SHA-0의 알고리즘과의 차이점 2)를 해결하기 위해 다음과 같이 A의 값은 유지한 채 기존 워드의 값 W0에서 W로 바꿔준다.
(A <<< 5) ⊞ F ⊞ E ⊞ K ⊞W0i[j] = (A <<< 5) xor F xor E xor K xor Wi[j]
그런데 이렇게 만들어진 새로운 워드열 W[ · ]는 16개의 워드에서 확장 알고리즘을 통해 생긴 워드열과는 거리가 멀다. 이 문제를 해결하기 위해 아주 중요한 점화식을 발견할 필요가 있다. 그 점화식은 B, C, D, E, F가 A로 표현 가능하다는 사실을 함축한다.
위 점화식을 자세히 들여다 보자. 만약 j 번째에서 워드의 값이 변하면 Aj의 값이 바뀌고, 그 충격은 그 턴을 포함해서 총 6 턴(즉, j, j+1, … , j+5) 동안 남아서 A의 값에 영향을 준다. 그리고 이미 변해 버린 A 값들에 의해 j+6번째 이후의 턴에서도 거의 모든 A 값이 변해 버릴 것임을 알 수 있다. 그런데 j+1, … , j+5번째 턴에서의 충격을 무효화하기 위해 (즉, Aj+1, … ,Aj+5의 값이 안 변하도록 하기 위해) 워드의 값을 적절히 바꿔줄 수가 있는데, 이렇게 처리한 경우 j+6번째 이후의 A 값에 전혀 영향을 주지 않음을 알 수 있다. (A의 점화식을 봐라!) 즉, 적절히 워드의 값을 바꿔줌으로써 j번째의 A 값만 바뀌고 나머지 전부는 그대로가 되도록 할 수 있는 것이다.
위 관찰 결과를 본격적으로 이용해 볼 생각이다. 위에서 설명한 방법을 토대로 우선 다음과 같은 워드열의 변화를 줄 수 있다.
여기서 j의 범위에 주목할 필요가 있다. 위와 같이 워드에 변화를 주는 경우 j번째 턴에서 Aj의 값이 바뀌어 버린다는 것을 분명히 언급했다. 그런데 한 블록단위 메시지를 처리할 때 출력되는 CV[0], … , CV[5]의 값이 원래 SHA-0의 솔루션의 출력값과 다르면 안 되므로 A75, A76, A77, A78, A79의 값이 바뀌어 버리는 것은 옳지 못하다. 따라서 j의 값의 상계를 75보다 작게 설정한 것이다. 그런데 나머지 5개의 워드의 xor 확장조건이 문제가 된다. 하지만 맨 처음의 16개의 워드를 아무렇게나 고치면 shock_mitigation 알고리즘에 의해 맨 뒤의 5개의 워드도 무작위적으로 값이 변하게 되어서 쉽게 해결될 것 같지는 않다. Brute-force 알고리즘을 쓰더라도 그 확률은 너무 작다; 임의의 5자리 워드열이 하필 내가 원하는 특정 워드열일 확률인 1/2160이다. 233번 계산을 할 때의 시간이 대략 1시간 정도임을 감안하면, 우주의 시간으로도 풀 수 없다. (이 시간은 시행착오로 알아낸 것이다.)
문득 이런 생각이 떠올랐다. 분명 맨 앞의 16개의 워드에서 딱 하나만 바꾸더라도 특정 지점 이후부터 A의 값이 바뀌기 시작한 뒤, 그 충격을 제하기 위해 shock_mitigation 알고리즘으로 몇 개의 워드의 값을 바꾸고, 또 xor 확장조건에 의해 다른 워드들의 값이 바뀌는 연쇄작용이 일어난다. 그런데, shock_mitigation 알고리즘으로 인해 바뀐 워드들이 딱 xor 확장조건을 만족하도록 만들 수는 없을까? 그러면 그 골치아픈 연쇄작용은 자연스럽게 해결되기 때문이다. 그것을 찾아내기 위해 우선 Aj, 16 ≤ j ≤ 74가 맨 처음 16개의 워드와 어떻게 상호작용하는지 이해할 필요가 있다. 그 상호작용은 다음 표에 자세히 제시돼 있다. 표를 읽는 방법은, 예를 들면 W[16]의 경우 0과 15 칸에 노랗게 색칠돼 있으므로 W[16] = W[0] xor W[15]라는 것으로 본다.
표를 보면 금세 계단식 모양을 눈치챌 수 있을 것이다. 이 위화감이 문제를 푸는 열쇠로 작용할 것이다. 다시 문제로 돌아가 지금 찾아내려고 하는 것은 shock_mitigation 알고리즘을 적용했는데 xor 확장조건도 덩달아 만족하는 케이스다. 조금만 생각해 보더라도 워드 하나의 변화 가지고는 이를 만족시킬 수 없고, 당장 생각나는 것은 맨 앞의 16개의 워드 중 6개의 워드가 한 세트로 다 같이 변하면 가능할 것 같다는 점이다. 즉, 워드 W[k1]이 어떤 j에 대해 W[j]의 값을 변화시키고, shock_mitigation을 실행한다. 그런데 하필 W[k2]가 W[j+1]의 변화와 대응되어서, 굳이 W[j+1]에서 shock_mitigation을 하지 않아도 되는 것이다. 그리고 W[k3], W[k4], W[k5], W[k6]에 대해서도 동일하게 적용될 수 있다. 이렇게 되면 A의 값을 유지한 채로 W[75], W[76], W[77], W[78], W[79]에 접근할 수 있을 것이다. 적당한 변화를 통해 마지막 워드의 xor 확장조건을 만족시키면 하나의 블록 단위 메시지를 성공적으로 처리한 것이다.
이제 중요한 질문은 그러한 6개의 워드를 찾아낼 수 있는가이다. 중요한 것은 워드 W[kp+1]가 상호작용하는 자리는 W[kp]와 비교하여 딱 한 자리만큼 뒤라는 점이다. 방금 주목한 계단 모양을 상기하면 아주 쉽게 그러한 워드세트의 후보를 추려낼 수 있게 된다.
위의 세트들 중 5, 6, 7, 8 번째 세트를 사용해 보자. 가급적 IF 조건(0 ≤ j ≤ 19)을 피하고 싶어서 앞의 것들을 선택하지 않았다. 이에 대한 논의는 바로 뒤에 더 자세히 이뤄진다. 각 후보 옆에 대응시킨 워드들은, 그 세트로 인해 값이 변하는 워드들이다. 잠깐 A의 점화식을 살펴보도록 하자.
누누히 강조하지만 A의 값이 변하는 순간은 shock_mitigation이 일어나는 순간뿐이다. W[4]에서 x 번째 비트의 값을 뒤집는 5 번째 세트(W[4], W[5], W[6], W[7], W[8])를 이용하려고 하는 경우 마지막으로 shock_mitigation이 일어나는 시점이 j = 71에서의 시점이므로, W[75]에서 x - 30 (mod 32) 번째 비트의 값이 뒤집힌다. 이러한 관계는 다음 그림에 모두 제시돼 있다. (단, 비트의 순서는 최좌측에서부터 떨어진 거리이다.)
위 그림에서 파란 선은 영향을 주고받는 관계이다. 따라서 (W[7], ..., W[12])로 W[79]를 비트단위로 바꾸고, 그 뒤 (W[6], ..., W[11])로 W[78]을 비트단위로 바꾸는 식으로 해야 할 것이다. 그렇게 바꾸었을 때 절묘하게 W[75]도 바뀔 수 있게, W[15]를 미리 바꾸어 놓으면 되겠다. 다만 빨간색으로 칠한 부분이 있어 비트 단위로 표적워드를 고쳐나가는 방법이 까다로울 것 같다. 하지만 더 큰 문제는 5개의 워드 세트의 후보를 골랐던 과정은 단지 shock_mitigation과 xor의 타이밍을 적절히 맞춘 것뿐이라는 점이다. 정말 중요한 점은 그 워드 세트 후보가 정말로 shock_mitigation이 가능한지이다. 가장 신경 쓰이는 점은 f 인데, 몇 차례 시행착오를 해본 바로는 그 결과가 절망스럽다. 마지막 구간의 f 가 XOR이었으므로 암묵적으로 shock_mitigation 알고리즘이 XOR 함수에 최적화되도록 했지만 그 결과가 IF와 MAJ 함수의 결과와 동일하지 않다. 다음을 보면 그 차이를 확인할 수 있다.
위 표를 보면 XOR 함수는 B, C, D 중 하나의 워드 내 한 비트의 값이 바뀌면 그 비트에 해당하는 자리의 논리값도 바뀐다. 따라서 이를 상쇄하기 위해 워드의 해당 비트의 값을 바꿔 주는 것(0이면 1, 1이면 0으로)이다. MAJ 함수가 B, C, D 중 하나의 워드 내 한 비트의 값이 바뀌어서 도출되는 논리값이 바뀌는 경우는 다른 두 워드의 해당 자리 비트가 서로 다른 값인 경우이다. 확률로 따지면 1/2이 된다. IF 함수도 다른 경우의 조합으로 확률이 1/2가 된다. 앞서 워드 세트를 선택할 때 IF 함수를 건너 뛰기 위한 시도가 있었던 까닭이다.
하지만 MAJ가 적용되는 구간을 뚫기란 여간 쉬운 일이 아니다. 대개 10번 이상의 shock_mitigation이 일어나는데, 이때 XOR에 최적화된 shock_mitigation을 적용하면 매번 1/8의 확률이 적용되어(1/2이 세 번) 총 확률 1/230으로 해결할 수 있다. 하지만 이것은 단일 비트에 대한 확률로 모든 비트에 대한 확률을 살펴보면 끔찍이 낮은 확률이 돼 버린다. 설사 비트 단위로 고치는 방법이 있더라도, 이 MAJ 구간을 뚫는 것이 어려워서 앞의 논의가 완전히 무의미해진다.
문득 이런 생각이 스쳤다. 과연 위 풀이는 실제 SHA-0의 해를 적극적으로 활용하고 있는가? 전혀 그렇지 않다. 위 풀이를 보면 그저 무작위적인 워드열을 부여받고, 그 끝 값을 고정시켜야 하는 그런 문제의 솔루션 같아 보인다. 만약 위의 풀이가 가능하다면, 임의의 워드열과 같은 해시값을 갖는 워드열을 찾을 수 있음을 의미할 텐데 분명 SHA-0는 자타가 공인하는 약한 충돌 저항성(weak collision resistant) 해시함수이다. 따라서 충돌쌍을 찾는 과정에서 위 풀이를 선택한 것은 너무 돌아간 게 아닌가 싶다.
그런데 좀 더 생각해 본 결과 위 풀이 전부가 틀린 게 아니라 딱 하나 잘못된 점이 있었던 것이다. 실제 SHA-0의 해를 이용하는 것이 아니라 직접 충돌쌍을 구하는 것이다. 어쩌면 Wang의 선구적인 방법을 자력으로 단 몇 주만에 이해해 버렸는지 모르겠다.
random_generator는 쉽게 구현할 수 있을 것이다. 한편 위 알고리즘을 이해하기 위해서는 선형성을 이해할 필요가 있다. 즉, (W[4], W[5], W[6], W[7], W[8], W[9])에 대한 xor 및 shock_mitigation을 적용한 뒤, (W[8], W[9], W[10], W[11], W[12], W[13])에 대한 xor 및 shock_mitigation을 적용하는 것과 미리(W[4], W[5], W[6], W[7], W[8], W[9])와 세트 (W[8], W[9], W[10], W[11], W[12, W[13]])에 대한 xor을 적용한 뒤 shock_mitigation을 적용하는 것이 동일한 워드열, A 배열을 생성한다는 것이다. 이것은 기본적으로 처음의 워드 16개가 다른 모든 것들을 결정하기 때문에 나오는 성질이다.
더 엄밀히 증명하자면, 임의의 j 번째 비트에서 위 선형성이 성립함을 보여야겠다. 우선 첫 번째 경우 무엇이 바뀌는지 살펴보자. 우선 shock_mitigation의 성질로 인해 A[j]의 값만 바뀔 뿐 다른 A 값은 바뀌지 않는다. 또한 W[j], W[j+1], W[j+2], W[j+3], W[j+4], W[j+5]가 바뀐다. 이는 두 번째 경우도 마찬가지이다. 그런데 워드는 전적으로 xor 조건에 의해 결정되고, xor은 결합법칙이 잘 성립하므로 바뀌어진 워드 값은 두 경우 동일하다. 그리고 A[j]는 W[j]가 같으면 같아지는 값이므로, 결국 모든 변화가 동일함을 발견할 수 있다. (참고로, 비트 단위로 shock_mitigation을 적용하는 것과 전체적인 변화는 같음을 위에서 언급했다; "shock_mitigation 알고리즘으로 인해 변한 워드들이 딱 xor 조건을 만족하도록 할 수 없을까?")
xor 결합법칙: (A xor W_1) xor W_2 = A xor (W_1 xor W_2)
워드 세트를 (W[4], W[5], W[6], W[7], W[8], W[9]), (W[8], W[9], W[10], W[11], W[12], W[13])으로 선택한 까닭:
1) 두 세트를 적용해서 W[75], W[76], W[77], W[78], W[79]의 값이 변하지 않기를 기대한다. 2) 가급적 IF 구간에 놓이는 것을 피하려고 했다. 3) MAJ 구간에서 겹치지 않는 구간이 고작 2개에 불과하다. (★)
위와 같이 임의로 워드열 자체를 바꿔가면서 운 좋게 MAJ 구간에서 XOR에 최적화된 shock_mitigation 알고리즘이 통과하기를 기대하는 것이다. 그런데 이런 의문이 들 수 있다. 단일 비트에 대해 위와 같이 뚫을 수 있는 확률이 1/230임을 언급했다. 그런데 두 개의 워드 세트에 대한 것이므로 확률의 곱셈법칙을 적용해서 그 확률이 1/260이 되지 않을까? 하지만 위의 선형성을 잘 보면 오히려 그 확률이 대폭 줄어듦을 알 수 있다. 예를 들어 다음을 보자.
두 세트가 A41에서 순차적으로 shock_mitigation을 일으키는 상황을 고려하자. (그래도 된다는 것은 바로 위에서 언급했다.) 이때 예상치 못하게 값이 달라질 수 있는 순간은 A41가 f 안에 있는A43, A44, A45이다. 만약 이 세 워드 중 하나라도 값이 통제되지 않으면 A45 이후의 A 값은 예상할 수 없는 값을 갖는다. 따라서 A43, A44, A45가 예상한 바대로 되도록 1/8의 확률을 기대할 필요가 있다. 실은 이 경우 언제나 1의 확률로 예상한 값이 나온다. (4, 5, 6, 7, 8, 9) 세트의 shock_mitigation 과정에서 A43가 예상하지 못한 값을 갖는다고 생각해 보자. 그 이유는 x 번째 위치에 있는 한 비트의 값이 바뀐 A41 때문으로 A43의 x 번째 비트에서 오류가 발생할 수 있다. (이때 A의 값보다 워드의 값을 고정한다고 가정했다.) 분명히 A40 <<< 30의 x 번째 비트와 A39 <<< 30의 x 번째 비트의 값이 같았기 때문일 것이다. 그런데 이는 (8, 9, 10, 11, 12, 13)도 마찬가지의 상황에 직면한다. 그러면 A43의 x 번째 비트에서 또다시 오류를 발생시킨다. 중요한 것은 두 번의 오류가 발생하면 다시 원상태로 돌아온다는 점이다. 따라서 (4, 5, 6, 7, 8, 9)과 (8, 9, 10, 11, 12, 13)이 같은 지점을 공격하면 언제나 1의 확률로 XOR 함수에 최적화된 shock_mitigation 알고리즘을 적용할 수 있다.
그럼에도 불구하고 문제가 되는 구간이 몇 개 있다. j = 52, 53이 교집합이 되는 구간이 아니고, j = 4와 j = 8도 (IF가 적용되는 구간이므로) 문제의 소지가 있다. 각 경우 1/8 씩의 확률이 적용되므로 총 확률은 1/4096이 될 것이다. 충분히 쉽게 풀 수 있는 확률이다.
두 세트가 성공적으로 MAJ 구간을 통과하면, 각 세트가 성공적으로 W[75] ~ W[79]의 특정 비트 값을 바꾸었으므로 결국 W[75] ~ W[79]의 값이 변하지 않게 만든다. 예를 들어, W[76] = W[1] xor W[5] xor W[9] xor W[13]인데, (4, 5, 6, 7, 8, 9) 세트에 의해 W[76]의 x - 5 (mod 32)번째 비트와 x - 30 (mod 32)번째 비트가 뒤집힌다. 그런데 (8, 9, 10, 11, 12, 13) 세트에 의해서 W[76]의 x - 5 (mod 32)번째 비트와 x - 30 (mod 32)번째 비트가 또 뒤집힌다. 두 번 뒤집히므로 값은 그대로이다. 따라서 Aj, 75 ≤ j ≤ 79의 값이 일정하므로 같은 해쉬값을 출력하게 된다.
이제부터 충돌쌍을 구하는 과정은 굉장히 단순해졌다. 다음 소스를 돌려보았고, 0.194 초 동안의 751번의 반복계산 결과 충돌쌍을 얻어냈다.
#include <stdio.h>
#include <stdlib.h>
unsigned int Rotation(unsigned int A, int j){
return (A << j) | (A >> 32 - j);
}
int main(int argc, char *argv[]) {
unsigned int W[2][80] = {
{
0x5b1daef2, 0x7743c95c, 0x7791a30f, 0xe9eccf35,
0xf0243d38, 0xf0241d45, 0x5bfc9e7d, 0x081a4849,
0x792c2bdf, 0x20f93600, 0x6cab315f, 0x8743ef19,
0xe3b9fe6c, 0x96f23b89, 0x2d1c48e0, 0x398c6f50
},
{
0x80000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000200
}
};
int i, count = 0;
unsigned int CV[5];
unsigned int A, B, C, D, E, K, T, F;
unsigned int note_A, note_B, note_C, note_D, note_E;
unsigned int a[80], note_a[80];
CV[0] = 0x67452301;
CV[1] = 0xEFCDAB89;
CV[2] = 0x98BADCFE;
CV[3] = 0x10325476;
CV[4] = 0xC3D2E1F0;
while(1){
printf("%d\n", ++count);
A = CV[0];
B = CV[1];
C = CV[2];
D = CV[3];
E = CV[4];
for(i = 16; i < 80; i ++)
W[0][i] = W[0][i - 1] ^ W[0][i - 16];
for(i = 0; i < 80; i ++){
if(i < 20){
K = 0x5A827999;
F = (B&C) | ((~B)&D);
}
else if(i < 40){
K = 0x6ED9EBA1;
F = B^C^D;
}
else if(i < 60){
K = 0x8F1BBCDC;
F = (B&C) | (B&D) | (C&D);
}
else{
K = 0xCA62C1D6;
F = B^C^D;
}
T = Rotation(A, 5) ^ F ^ E ^ K ^ W[0][i];
B = Rotation(B, 30);
E = D;
D = C;
C = B;
B = A;
A = T;
a[i] = A;
}
note_A = A;
note_B = B;
note_C = C;
note_D = D;
note_E = E;
A = CV[0];
B = CV[1];
C = CV[2];
D = CV[3];
E = CV[4];
W[0][4] = W[0][4] ^ 0x00000001;
W[0][5] = W[0][5] ^ Rotation(0x00000001, 5);
W[0][6] = W[0][6] ^ 0x00000001;
W[0][7] = W[0][7] ^ Rotation(0x00000001, 30);
W[0][8] = W[0][8] ^ Rotation(0x00000001, 30);
W[0][9] = W[0][9] ^ Rotation(0x00000001, 30);
W[0][8] = W[0][8] ^ 0x00000001;
W[0][9] = W[0][9] ^ Rotation(0x00000001, 5);
W[0][10] = W[0][10] ^ 0x00000001;
W[0][11] = W[0][11] ^ Rotation(0x00000001, 30);
W[0][12] = W[0][12] ^ Rotation(0x00000001, 30);
W[0][13] = W[0][13] ^ Rotation(0x00000001, 30);
for(i = 16; i < 80 - 1; i ++)
W[0][i] = W[0][i - 1] ^ W[0][i - 16];
for(i = 0; i < 80; i ++){
if(i < 20){
K = 0x5A827999;
F = (B&C) | ((~B)&D);
}
else if(i < 40){
K = 0x6ED9EBA1;
F = B^C^D;
}
else if(i < 60){
K = 0x8F1BBCDC;
F = (B&C) | (B&D) | (C&D);
}
else{
K = 0xCA62C1D6;
F = B^C^D;
}
T = Rotation(A, 5) ^ F ^ E ^ K ^ W[0][i];
B = Rotation(B, 30);
E = D;
D = C;
C = B;
B = A;
A = T;
note_a[i] = A;
}
if(A == note_A &&
B == note_B &&
C == note_C &&
D == note_D &&
E == note_E)
break;
for(i = 0; i < 16; i ++)
W[0][i] = note_a[i + 64];
}
for(i = 0; i < 40; i ++)
printf("%d) %X %X\t%d) %X %X\n", i, a[i], note_a[i], i+40, a[i+40], note_a[i+40]);
for(i = 0; i < 16; i ++){
if(i % 4 == 0) printf("\n");
printf("%X ", W[0][i]);
}
W[0][13] = W[0][13] ^ Rotation(0x00000001, 30);
W[0][12] = W[0][12] ^ Rotation(0x00000001, 30);
W[0][11] = W[0][11] ^ Rotation(0x00000001, 30);
W[0][10] = W[0][10] ^ 0x00000001;
W[0][9] = W[0][9] ^ Rotation(0x00000001, 5);
W[0][8] = W[0][8] ^ 0x00000001;
W[0][9] = W[0][9] ^ Rotation(0x00000001, 30);
W[0][8] = W[0][8] ^ Rotation(0x00000001, 30);
W[0][7] = W[0][7] ^ Rotation(0x00000001, 30);
W[0][6] = W[0][6] ^ 0x00000001;
W[0][5] = W[0][5] ^ Rotation(0x00000001, 5);
W[0][4] = W[0][4] ^ 0x00000001;
printf("\n");
for(i = 0; i < 16; i ++){
if(i % 4 == 0) printf("\n");
printf("%X ", W[0][i]);
}
printf("\n");
return 0;
}
여담으로 이제 약한 충돌 저항성에 대해서 검토해 보자. 과연 위 알고리즘으로 그 충돌 저항성을 깰 수 있을까? 필자는 깰 수 없다고 생각한다. 위에서처럼 (W[4], W[5], W[6], W[7], W[8], W[9])와 (W[8], W[9], W[10], W[11], W[12], W[13])을 처리해서 맨 마지막의 워드를 중립적으로 유지하면서 워드 자체에 변화를 줄 수 있다고 생각할 지 모르겠다. 다만 이 경우에도 1/4096이라는 확률이 적용된다. 우리가 선택할 수 있는 부분은 그 두 세트를 포함한 세트쌍과 그 세트에서 선택할 수 있는 비트의 위치이다. 세트들을 그룹 지으면 3, 3, 2, 2개씩 묶을 수 있는데, 각 그룹에서 2개씩 뽑는 경우와 선택한 비트의 위치의 크기인 32를 곱하면 256이 된다. 확실히 선택의 여지가 없는 경우가 존재할 듯 싶다.
최근댓글