몬테 카를로 테스트 ( Monte Carlo Test )

Monte Carlo Test 검사는 대칭키 암호 또는 해시 알고리즘의 안전성과 무작위성을 검증하기 위해 사용하는 통계적 방법 중 하나입니다. 대칭키 암호 알고리즘은 동일한 키를 사용하여 데이터를 암호화하고 복호화하는 방식인데, 이러한 알고리즘의 보안성을 평가하는 중요한 절차 중 하나가 Monte Carlo Test입니다.

다음은 몬테카를로 테스트를 위한 psedo 코드이다.

참고 자료 [Cipher] [Hash]

해시 함수의 몬테 카를로는 두가지 방식이 있다 Standard 와 Alternate 방식이다.

SHA-1 and SHA-2 Standard Monte Carlo Test

For j = 0 to 99
    A = B = C = SEED
    For i = 0 to 999
        MSG = A || B || C
        MD = SHA(MSG)
        A = B
        B = C
        C = MD
    Output MD
    SEED = MD

SHA-1 and SHA-2 Alternate Monte Carlo Test:

INITIAL_SEED_LENGTH = LEN(SEED)
For j = 0 to 99
    A = B = C = SEED
    For i = 0 to 999
        MSG = A || B || C
        if LEN(MSG) >= INITIAL_SEED_LENGTH:
            MSG = leftmost INITIAL_SEED_LENGTH bits of MSG
        else:
            MSG = MSG || INITIAL_SEED_LENGTH - LEN(MSG) 0 bits
        MD = SHA(MSG)
        A = B
        B = C
        C = MD
    Output MD
    SEED = MD

대칭키 암호화의 몬테 카를로 방식은 운영 모드마다 각각의 방식이있다.
그리고 암호화 / 복호화 각각의 방식을 사용하다.
참고로 복호화 경우 암호화에서 PT->CT 로 대응 되며 암호화->복호화를 대칭된다구 보면 된다.

AES Monte Carlo Test - ECB mode

Encrypt

Key[0] = KEY
PT[0] = PT
For i = 0 to 99
    Output Key[i]
    Output PT[0]
    For j = 0 to 999
        CT[j] = AES_ECB_ENCRYPT(Key[i], PT[j])
        PT[j+1] = CT[j]
    Output CT[j]
    AES_KEY_SHUFFLE(Key, CT)
    PT[0] = CT[j]

AES Monte Carlo Test - CBC mode

Encrypt

Key[0] = KEY
IV[0] = IV
PT[0] = PT
For i = 0 to 99
    Output Key[i]
    Output IV[i]
    Output PT[0]
    For j = 0 to 999
        If ( j=0 )
            CT[j] = AES_CBC_ENCRYPT(Key[i], IV[i], PT[j])
            PT[j+1] = IV[i]
        Else
            CT[j] = AES_CBC_ENCRYPT(Key[i], PT[j])
            PT[j+1] = CT[j-1]
    Output CT[j]
    AES_KEY_SHUFFLE(Key, CT)
    IV[i+1] = CT[j]
    PT[0] = CT[j-1]

AES Monte Carlo Test - OFB mode

Encrypt

Key[0] = Key
IV[0] = IV
PT[0] = PT
For i = 0 to 99
    Output Key[i]
    Output IV[i]
    Output PT[0]
    For j = 0 to 999
        If ( j=0 )
            CT[j] = AES_OFB_ENCRYPT(Key[i], IV[i], PT[j])
            PT[j+1] = IV[i]
        Else
            CT[j] = AES_OFB_ENCRYPT(Key[i], PT[j])
            PT[j+1] = CT[j-1]
    Output CT[j]
    AES_KEY_SHUFFLE(Key, CT)
    IV[i+1] = CT[j]
    PT[0] = CT[j-1]

AES Monte Carlo Test - CFB128 mode

Encrypt

Key[0] = Key
IV[0] = IV
PT[0] = PT
For i = 0 to 99
    Output Key[i]
    Output IV[i]
    Output PT[0]
    For j = 0 to 999
        If ( j=0 )
            CT[j] = AES_CFB128_ENCRYPT(Key[i], IV[i], PT[j])
            PT[j+1] = IV[i]
        Else
            CT[j] = AES_CFB128_ENCRYPT(Key[i], PT[j])
            PT[j+1] = CT[j-1]
    Output CT[j]
    AES_KEY_SHUFFLE(Key, CT)
    IV[i+1] = CT[j]
    PT[0] = CT[j-1]

마무리

몬테카를로 테스트는 암호 또는 해시 함수의 구현을 검증 하기 위해 사용된다.
CMVP 또는 FIPS 인증을 받기 위해서는 MCT 테스트를 요구 하기 때문에 필수로 구현이 필요하다.