암호학에서 CBC 모드에 대한 질문
게시판 카테고리를 어디로 정해야 할지 몰라서 자유 게시판에 올립니다.;;
암호학 하는 사람도 없는데, 공부하려고 하다 보니 힘드네요. Linux forum이지만 똑똑한 분들이 많이 계신거 같아서 답을 얻을 수 있을까 하여 질문 올려봅니다.
우선은, Bruce schneier님이 쓰신 'Applied Cryptography'를 보고 있구요. mode of operation중에 cipher block chaining(CBC)을 공부하다가 의문이 생겼습니다.
electronic code book(ECB)에서 제공하지 못하는 semantic security를 CBC는 chaining이라는 기법을 통해 제공해주고 있는데, 저자가 CBC의 Security problem에 대해 얘기하기를 plaintext pattern 이 chaining에 의해 숨겨질 지라도 매우 큰 메시지에서는 pattern들을 가지게 된다고 하네요.
왜냐하면 birthday paradox에 의해서 2^(m/2) block 후에 동일한 block이 예상된다고 하는데, 제가 궁금한 점은 2^(m/2) block을 시도해서 만일 동일한 block을 찾았다고 하더라고 어떻게 그 block이 동일한 block인지를 아느냐 하는 점과 또한 이것을 공격자가 알게됨으로써 왜 취약해질수 있느냐(예를 들어, block replay가 가능한지)입니다. 혹시 암호학을 공부하시는 분이 계시다면 제 글을 읽어주셨으면 합니다. ^^;
또 다른 질문으로는 제가 지금 쓰는 이런 유형의 질문이 본 포럼에 적합하지 않다면은 국내 또는 외국에 암호학을 전문으로 토의 및 질문 할 수 있는 포럼같은게 있나요? 아시는 분..
읽어주셔서 감사합니다.~_~
birthday paradox의
birthday paradox의 문제점은 hash에서 처음 제기되었는데, 원래 값이 다르다고 할 지라도 상당히 높은 확률로 해쉬 값이 같은 두 값을 찾기가 쉽다는 것입니다. CBC는 chaining때문에 하나의 비트 값만 바껴도 전체 값이 크게 영향을 받지만, MAC등을 첨부해서 이 값이 도중에 훼손 또는 변경되었는지 여부를 검출할 때 상당히 높은 확률로 공격자가 MAC이 같은 다른 메시지를 첨부할 수 있다는 것이 문제입니다. 즉, 송신 측에서 인증해서 첨부한 MAC을 이용해서 다른 메시지를 보낼 경우, 수신 측에서는 이를 아무런 의심 없이 받을 수 있다는 것이 문제지요.
답변 감사합니다.
답변 감사합니다. 그렇다면 birthday paradox에 근거한 CBC의 문제점은, CBC-MAC을 예로 들어서, 공격자가 변경한 메시지를 적법한 MAC값과 함께 보낼 확률이 높다라는 것인가요? 따라서 이러한 공격에는 취약해질 수 있다라는 것을 저자의 의도로 제가 받아 들이면 맞는지 모르겠네요. 한가지 더 질문 하자면, 앞서 언급한 MAC을 예로 들지 않았을때, 공격자가 CBC에서 패턴을 알아내어 block replay를 할 수 있는 상황이 있을까요? 자꾸 질문만 하게 되는 군요..;
단순 block replay라면
단순 block replay라면 굳이 패턴을 알아낼 필요가 있을까요? 메시지 내부적으로 sequence#따위가 있어서 replay attack을 방지하지 않는 한 패턴을 알아내고 block을 다시 보낼 필요는 없다고 생각됩니다. CBC의 원래 목적은 plain text를 cipher text에서 알아내기 '힘들게' 만드는 것이지 '불가능'하게 만드는 건 아니라고 생각합니다. 질문하신 내용에서 패턴을 알아내야 가능한 block replay가 정확히 어떤 것인지는 잘 모르겠습니다.
예. 메시지 1
예.
메시지 1
블럭 번호 1 2 3 4
plaintext 앨리스 밥 만원 1시
ciphertext QQQQ WWWW EEEE RRRR
메시지 2
블럭 번호 1 2 3 4
plaintext 앨리스 이브 백원 2시
ciphertext AAAAA SSSS DDDD FFFF
위의 예에서 각 블럭 번호의 의미는 1번: 송신자 2번: 수신자 3번:돈 4번:시간이며 은행에서 계좌이체를 한다고 가정하겠습니다. 또한 MAC(Message Authentication code)도 각 메시지에 포함되어 있지 않습니다. 각 메시지는 은행 서버에 보내져서 계좌이체를 실행할 수 있도록 합니다.
이때, 메시지 1에서 블럭 번호 3번에 해당하는 정보가 '만원'인데 이것을 이브가 메시지 2번의 블럭 3번에 끼워 넣어서 새로운 메시지 3을 만든 후 메시지 3을 은행에 보낸다고 한다는 것을 block replay라는 용어로 앞서 드린 질문에서 사용하였습니다. 그런데 CBC에서는 이전 block에서 생성된 cipherblock을 feedback으로써 chaining하여 암호화 하기 때문에(동일한 메시지가 암호화 할때마다 다른 ciphertext로 암호화 되기때문에) 이러한 block replay 공격이 어려워지는 것이다 까진 이해가 되는데요. MAC을 생각 하지 않았을때, 단순히 이브가 많은 메시지를 받아보고 패턴을 분석해서 메시지 1번의 3번 블럭에 해당하는 정보인 '만원'의 값을 메시지 2번의 3번 블럭에 끼워맞출 수 있느냐 하는게 궁금했습니다.
그런데 장황하게 예제를 그려가며 쓰다보니, 위의 상황에서 MAC을 사용하여 각 메시지의 무결성 및 인증성 검사를 해야하는게 당연하다는 생각이 드는군요.. 따라서 SoulreaveR님이 답변해주신MAC에 대한 birthday attack의 성공 확률이 높아지므로 CBC에도 문제가 있을 수 있다가 저자가 제기한 문제라고 추측해봅니다. 원문에 나오기로는 딱 세줄로 써놔서 너무.. 이해하기가 어려웠는데 답변 감사합니다.
원문 -
Finally, although plaintext patterns are concealed by chaining, very long messages will still have patterns. The birthday paradox predicts that there will be identical blocks after 2^(m/2)blocks, where m is the block size. For a 64-bit block size, that's about 34 gigabytes. A message has to be pretty long before this is a problem.
다시 또 생각해보면 저자가 의도했던 본래 목적이 뭐였는가.. 의문이 생기네요. 알쏭달쏭..
저자가 말하고자
저자가 말하고자 한건 이런 것 같네요. ECB처럼 단순 치환식 암호화의 단점은 메시지의 통계적인 수치를 숨기지 못한다는 점이죠. 이를테면 영문 메시지라고 가정할 경우 나타나는 숫자를 세어서 가장 많이 나오는 글자를 't'로 가정하고 풀어나가는 방식이 가능하기 때문에, CBC는 이걸 없애기 위해서 암호화 결과에 이전 block의 암호화 결과를 연결해서 통계적인 성질을 없애는 거죠.
문제는 이렇게 chaining 되는 block 자체가 길이가 한정되어 있기 때문에, 언젠가는 n 번째 cipher block과 동일한 block이 2+n^(m/2) 쯤에서 나오게 되고, 그렇다면 n+1번째 block과 2^(m/2)+1번째 block에 사용되는 cipher block이 값이 똑같기 때문에 두 block에 대해서는 통계적 성질이 사라지지 않게 되기 때문에 공격자가 이를 통해서 매우 긴 cipher text block의 통계적 성질을 이용해서 원본과 키를 유추할 수 있지 않나 이 얘기를 하는거 같습니다.
제가 써놓고도 뭔 소린지는 잘 모르겠네요.