기지평문공격

기지평문공격(旣知平文攻擊, Known Plaintext Attack, KPA)은 공격자가 평문과 평문을 암호화한 암호문을 모두 알고 있을 때 사용할 수 있는 암호해독 기법이다. 이미 알고 있는 평문과 암호문을 바탕으로 비밀 키를 알아내기 위해 사용한다. '기지'(旣知)란 "이미 알고 있다"는 뜻으로서, 기지평문공격은 알려진 평문 공격이라고 할 수 있다.

개요

암호학에서 기지평문공격은 공격자가 평문과 그를 암호화한 암호문을 모두 알고 있을 때 사용할 수 있는 암호 해독 기법들을 말한다. 이미 알고 있는 평문을 크립(crib)이라고 부르는데, 크립이라는 용어는 제2차 세계 대전 당시 암호 해독실인 블레츨리 파크(Bletchley Park)에서 유래했다. 암호해독가가 암호를 해독하기 위해 의미 없어보이는 암호문만 보아서는 많은 정보를 얻기 힘들지만 암호문 안에 이미 알고 있는 평문이 포함되어 있다면, 그 사실이 암호문과 평문 사이의 관계를 추정하기 위한 단서가 될 수 있다. AES 등의 현대 암호체계는 기지평문공격의 영향을 받지 않는 것으로 알려졌지만 예전 버전의 ZIP 파일 포맷에 사용되는 PKZIP 스트림 암호화 알고리즘은 기지평문공격에 취약하다. 이 알고리즘으로 암호화된 압축 파일은 압축 파일 안에 들어있는 파일의 일부라도 알아낼 수 있으면 전체 압축 파일을 해독 할 수 있다. 기지평문공격은 대칭키를 통해 이루어진 통신 채널을 공격하기 위해 주로 사용되며, 기지평문공격의 최종 목표는 복호키를 찾는 것이다.

역사

블레츨리 파크는 독일군 암호 기계인 에니그마(Enigma)를 해독하기 위해 크립 기반 공격을 여러 가지로 활용했다. 독일군 최고사령부는 크립 기반 공격의 위험을 잘 알고 있었고, 이를 피하기 위한 방법들을 사용했다. 그러나 최전선에서 싸우는 하급 장교들은 이 문제에 크게 주의하지 않았기 때문에, 암호 해독의 실마리를 주곤 했다. 예를 들어 독일군 기상관측병이 수뇌부에게 기상정보를 보낼 때, 군대 보고의 특성상 항상 정형화된 보고를 암호화해서 보냈다. 블레츨리 파크는 이 점과 해당 지역의 실제 날씨를 조합해, 기상관측병이 보내는 메시지가 어떤 내용일지를 추정할 수 있었다.

한편, 블레츨리 파크는 일부러 독일군에게 특정한 평문의 전송을 유도하기도 했다. 예를 들어 북해의 특정 지역에 기뢰를 투하하고, 그 시점에 해당 지역에서 보내는 해군의 암호문을 도청하면 거기에는 해당 지역의 위치와 기뢰에 관한 내용이 포함되어 있을 확률이 높았다. 블레츨리 파크는 독일군 포로에게서 독일군의 암호문이 숫자를 말로 풀어서 전송하고 있다는 정보를 얻기도 했다. 수학자 앨런 튜링(Alan Turing)은 이 정보를 이용해 전체 평문의 90%에 숫자 1에 해당하는 독일어 EIN이 포함되어 있다는 사실을 알아냈다. 튜링은 에니그마 암호 기계의 설정에 따라 EIN 이라는 단어가 암호화될 수 있는 모든 경우의 수를 작성한 후 EIN의 위치를 찾아내는 방법을 쓰기도 했다.

예제

• 구현

msg = '53%%#305))6*;4826)4%=\')4%);806*;48#8@60\'))85;1%(;:-%*8#83(88)5*#;46(;88*96*?;8)*%(;485);5*#2:*%(;4956*2(5*c4)8@8*;4069285);)6#8)4%%;1(%9;48081;8:8%1;48#85;4\')-485#528806*81(%9;48;(88;4(%?34;48)4%;161;:188;%?;'

# 알려진 평문이 있을 경우 사용 가능
# 이 암호문 중에 goodglass, mainbranch 단어가 있는 것을 알 때,

# 패턴을 비교
# 즉, 문자열을 선형으로 넘버링해서 비교(선형화 -> 선형공격)
# 실제 정규표현식 내부가 이런 식으로 구성

def make(hint):
    tmp = {}    # 순서를 저장
    res = 
    index = 0

    for c in hint:
        if c in tmp:
            res += tmp[c]
        else:
            # 없으면
            tmp[c] = str(index)
            # 단어에 대한 인덱스를 딕셔너리에 넣기

            res += str(index)
            # 리스트에 단어에 대칭하는 인덱스를 추가

            index += 1

    return res
    #return ':'.join(res)   # 리스트를 :로 구분지어 문자열로 반환

def find_pattern(msg, hint):
    pattern = make(hint)    # 선형화
    psize = len(hint)       # 선형화한 문자열의 길이
    pos = 0     # 암호문내에서 비교할 시작인덱스

    while True:
        data = msg[pos:pos+psize]
        # 시작점부터 문자열의 길이까지

        if len(data) < psize:
            # 길면 나가기
            break

        d_pattern = make(data)
        # data에 대한 패턴     

        if d_pattern == pattern:
            return data
        pos += 1

def dec(msg, key):
    pmsg =

    for c in msg:
        if c in key:
            c = key[c]

        pmsg = pmsg + c

    return pmsg

def main():
    print('---------------------------- 암호문 ------------------------------')

    print(msg)
    print()

    key = {}

    hint1 = 'goodgress'
    hint2 = 'mainbranch'

    result1 = make(hint1)
    print('1) 알려진 평문[goodgress]의 패턴 : {}'.format(result1))

    data = find_pattern(msg, hint1)

    index = 0
    for k in data:
        key[k] = hint1[index]
        index += 1

    print('2) 알려진 평문의 알파벳')
    print(' [+] {}\n'.format(key))

    result2 = make(hint2)
    print('3) 알려진 평문[mainbranch]의 패턴 : {}'.format(result2))

    data = find_pattern(msg, hint2)

    index = 0
    for k in data:
        key[k] = hint2[index]
        index += 1

    print('4) 알려진 평문의 알파벳')
    print(' [+] {}'.format(key))

    pmsg = dec(msg, key)

    print('-------------------- 찾은 알파벳으로 복호화 ----------------------')
    print(pmsg)

if __name__ == '__main__':
    main()

• 시연

d4tai1@ubuntu ~/crypto/10week python3 KPA.pv
---------------------------- 암호문 ------------------------------
53%%#305))6*;4826)4%=\')4%);806*;48#8@60\'))85;1%(;:-%*8#83(88)5*#;46(;88*96*?;8)*%(;485);5*#2:*%(;4956*2(5*c4)8@8*;4069285);)6#8)4%%;1(%9;48081;8:8%1;48#85;4\')-485#528806*81(%9;48;(88;4(%?34;48)4%;161;:188;%?;

1) 알려진 평문[goodgress]의 패턴 : 011203455
2) 알려진 평문의 알파벳
 [+] {'3': 'g', '%': 'o', '#': 'd', '0': 'r', '5': 'e', ')': 's'}

3) 알려진 평문[mainbranch]의 패턴 : 0123451367
4) 알려진 평문의 알파벳
 [+] {'3': 'g', '%': 'o', '#': 'd', '0': 'r', '5': 'a', ')': 's', '9': 'm', '6': 'i', '*': 'n', '2': 'b', '(': 'r', 'c': 'c', '4': 'h'}
-------------------- 찾은 알파벳으로 복호화 ----------------------
agoodgrassin;h8bisho='shos;8rin;h8d8@ir'ss8a;1or;:-on8d8gr88sand;hir;88nmin?;8snor;h8as;andb:nor;hmainbranchs8@8n;hrimb8as;sid8shoo;1rom;h8r81;8:8o1;h8d8a;h's-h8adab88rin81rom;h8;r88;hro?gh;h8sho;1t1;:188;o?;
d4tai1@ubuntu ~/crypto/10week

• 찾은 알파벳은 암호 대신 사용해서 출력해서 해독할 수 있다.
• 알려진 평문을 많이 얻을수록 해독률이 높아진다.

참고자료

• D4tai1, 〈Known Plaintext Attack(기지 평문 공격) 구현〉, 《티스토리》, 2019-05-31
• 〈기지 평문 공격〉, 《위키백과》
• 불곰, 〈알려진 평문 공격 (기지 평문 공격) - Known-plaintext attack〉, 《티스토리》, 2017-03-27
• 박진범, 〈암호 시스템 공격 기법〉, 《다음 블로그》, 2013-05-09

같이 보기

• 블레츨리 파크
• 암호화
• 복호키
• 대칭키

이 기지평문공격 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반