[암호학] 5. DES의 key는 왜 8비트가 버려지는가?

DES를 두번 사용하는 암호학 문제를 meet-in-the-middle attack 을 활용하여 풀고있었다.
그러나 key 값이 마지막에 1비트씩 차이가 났었지만 정답은 맞는 상황이 발생했다.

\xba\xc7\xb5\xf5는 문제에서 만든 key값이다.
\xbb\xc7\xb4\xf4는 내가 찾은 key값이다.

key의 값들이 최대 1비트씩 차이가 났었지만 정답을 맞추는 데에는 문제가 없었다. 왜그랬을까?
이유를 알기 위해서는 DES의 알고리즘을 확인해 볼 필요가 있다.

저번 블로그에서도 다뤘지만, DES의 KeySchedule은 다음과 같다.

여기서 보면 key는 64비트로 받는다. 하지만 PC-1 (permutation choice 1)을 지나면 56비트로 바뀐다.
즉, key의 64비트 중 8비트는 버려진다는 뜻이다.
내가 구한 key가 PC-1을 통과했을 때 같기만 하면 되기 때문에 꼭 완전히 전체의 key가 같을 필요는 없었다.

왜 DES의 key는 56비트만 사용할까?

‘패리티 비트(Parity Bit)’때문이다.
패리티 비트(Parity Bit)는 정보나 데이터를 전송 또는 저장할 때 오류가 발생했는지 검사하기 위해 덧붙이는 1비트이다.
따라서 실질적으로 key로서 유효한 값은 56비트이므로 PC-1을 지나면 버려진다.

DES의 key는 8바이트이고, 각 바이트의 LSB는 패리티 비트이다.
이 비트들은 해당 바이트의 1의 개수가 홀수 혹은 짝수가 되도록 설정된다.
1의 개수가 홀수면 홀수 패리티 (Odd Parity), 짝수면 짝수 패리티 (Even Parity) 라고 부른다.
만약 홀수 패리티를 이용하는 알고리즘에서 바이트의 1의 개수가 짝수면 오류가 발생한 것이다.

DES는 표준적으로 홀수 패리티를 사용한다.
예전 통신 환경에서는 전선이 끊어지거나 장비가 꺼져서 아무런 신호도 들어오지 않는 경우, 시스템이 이를 00000000이라는 유효 데이터로 오인할 위험이 있었다.
이는 홀수 패리티를 이용하면 즉시 오류가 발생했음을 알 수 있다.