과제중에 AES의 차분공격을 위해 AES의 DDT(differential distribution table)을 계산해야할 일이 있었다.
차분공격과 DDT에대한 개념은 넘겨두고 요점은 Sbox에 Δx의 차이를 가진 두 입력의 출력의 차이 Δy의 출현값 분포표를 계산하는 것이다.
계산방법등을 생략하면 리스트안에 지저분하게 값들이 append 되어있다.
물론 dict를 미리 선언하고 없으면 아이템을 추가한 뒤 이후에 사전에 존재하는 아이템일 경우 +1을 하는 방식으로 해도 괜찮지만 파이썬에는 대충 리스트안에 값들을 다 박아두면 이런 것들을 자동으로 해주는 장치가 있을 것이라는 믿음이 있었다.
Counter함수
파이썬으로 코드를 짜면 가장 편한 것은 이거 이렇게 한번에 해주는게 없을까? 하면 늘 있어준다는 것이다
예를 들면 다음 같은 리스트를 생각하자
[117, 199, 35, 203, 253, 70, 246, 132, 88, 67, 129, 148, 243, 94, 10, 250, 21, 170, 156, 179, 19, 222, 89, 107, 57, 90, 123, 198, 141, 60, 138, 33, 41, 224, 82, 160, 143, 104, 194, 173, 58, 83, 230, 185, 23, 109, 15, 101, 142, 76, 158, 136, 7, 226, 216, 114, 193, 166, 38, 254, 197, 2, 202, 207, 1, 45, 86, 127, 241, 154, 12, 204, 251, 117, 3, 62, 68, 212, 231, 99, 42, 53, 149, 124, 66, 80, 98, 153, 54, 239, 184, 112, 64, 118, 106, 47, 11, 228, 244, 37, 87, 245, 221, 195, 205, 105, 40, 93, 140, 115, 30, 200, 34, 186, 29, 235, 175, 227, 159, 49, 171, 242, 77, 126, 252, 236, 255, 31, 31, 255, 236, 252, 126, 77, 242, 171, 49, 159, 227, 175, 235, 29, 186, 34, 200, 30, 115, 140, 93, 40, 105, 205, 195, 221, 245, 87, 37, 244, 228, 11, 47, 106, 118, 64, 112, 184, 239, 54, 153, 98, 80, 66, 124, 149, 53, 42, 99, 231, 212, 68, 62, 3, 117, 251, 204, 12, 154, 241, 127, 86, 45, 1, 207, 202, 2, 197, 254, 38, 166, 193, 114, 216, 226, 7, 136, 158, 76, 142, 101, 15, 109, 23, 185, 230, 83, 58, 173, 194, 104, 143, 160, 82, 224, 41, 33, 138, 60, 141, 198, 123, 90, 57, 107, 89, 222, 19, 179, 156, 170, 21, 250, 10, 94, 243, 148, 129, 67, 88, 132, 246, 70, 253, 203, 35, 199, 117]
for 돌리면서 카운트 시킬려면 처음부터 사전을 선언한 뒤에 코드를 짰을 것 이다.
from collections import Counter
print("delta_x : {}".format(delta_x))
count=Counter(result)
print(count)
from collections import Counter 이 Counter함수가 카운트를 자동으로 해준다.
위의 리스트를 result라 할 때 위의 코드는 다음과 같은 결과를 준다
delta_x : 255
Counter({117: 4, 199: 2, 35: 2, 203: 2, 253: 2, 70: 2, 246: 2, 132: 2, 88: 2, 67: 2, 129: 2, 148: 2, 243: 2, 94: 2, 10: 2, 250: 2, 21: 2, 170: 2, 156: 2, 179: 2, 19: 2, 222: 2, 89: 2, 107: 2, 57: 2, 90: 2, 123: 2, 198: 2, 141: 2, 60: 2, 138: 2, 33: 2, 41: 2, 224: 2, 82: 2, 160: 2, 143: 2, 104: 2, 194: 2, 173: 2, 58: 2, 83: 2, 230: 2, 185: 2, 23: 2, 109: 2, 15: 2, 101: 2, 142: 2, 76: 2, 158: 2, 136: 2, 7: 2, 226: 2, 216: 2, 114: 2, 193: 2, 166: 2, 38: 2, 254: 2, 197: 2, 2: 2, 202: 2, 207: 2, 1: 2, 45: 2, 86: 2, 127: 2, 241: 2, 154: 2, 12: 2, 204: 2, 251: 2, 3: 2, 62: 2, 68: 2, 212: 2, 231: 2, 99: 2, 42: 2, 53: 2, 149: 2, 124: 2, 66: 2, 80: 2, 98: 2, 153: 2, 54: 2, 239: 2, 184: 2, 112: 2, 64: 2, 118: 2, 106: 2, 47: 2, 11: 2, 228: 2, 244: 2, 37: 2, 87: 2, 245: 2, 221: 2, 195: 2, 205: 2, 105: 2, 40: 2, 93: 2, 140: 2, 115: 2, 30: 2, 200: 2, 34: 2, 186: 2, 29: 2, 235: 2, 175: 2, 227: 2, 159: 2, 49: 2, 171: 2, 242: 2, 77: 2, 126: 2, 252: 2, 236: 2, 255: 2, 31: 2})
delta_x는 개인적으로 필요해서 들어있는 값이고 Counter 부분에 주목을 해보면 예쁘게 카운트해준 것을 볼 수 있다.
다만 카운트는 예쁜데 출력이 예쁘지가 않다. 가장 많이 나온 순서대로 두려고 한 것 같은데 이상태로는 값을 활용하기도 어렵고 카운트가 같은 값끼리는 뒤죽박죽이라 보기 눈아프다.
Counter 정렬하기 key OR value
Counter를 정렬하는 방법에는 두 가지가 있다. 위의 결과를 아이템 이름 순으로 할지, 카운터의 값(value)가 큰 순서대로 할지이다.
큰 순서대로 정렬하는 방법은 [Counter].most_common()이며 아이템의 이름으로 정렬하는 것은 sorted([Counter].items())이다.
count=Counter(result)
print(count)
print(count.most_common())
print(sorted(count.items()))
다음 세가지 출력의 결과를 보자. 순서대로 무가공, 카운트순서, 아이템이름순이다.
delta_x : 255
#Raw output
Counter({117: 4, 199: 2, 35: 2, 203: 2, 253: 2, 70: 2, 246: 2, 132: 2, 88: 2, 67: 2, 129: 2, 148: 2, 243: 2, 94: 2, 10: 2, 250: 2, 21: 2, 170: 2, 156: 2, 179: 2, 19: 2, 222: 2, 89: 2, 107: 2, 57: 2, 90: 2, 123: 2, 198: 2, 141: 2, 60: 2, 138: 2, 33: 2, 41: 2, 224: 2, 82: 2, 160: 2, 143: 2, 104: 2, 194: 2, 173: 2, 58: 2, 83: 2, 230: 2, 185: 2, 23: 2, 109: 2, 15: 2, 101: 2, 142: 2, 76: 2, 158: 2, 136: 2, 7: 2, 226: 2, 216: 2, 114: 2, 193: 2, 166: 2, 38: 2, 254: 2, 197: 2, 2: 2, 202: 2, 207: 2, 1: 2, 45: 2, 86: 2, 127: 2, 241: 2, 154: 2, 12: 2, 204: 2, 251: 2, 3: 2, 62: 2, 68: 2, 212: 2, 231: 2, 99: 2, 42: 2, 53: 2, 149: 2, 124: 2, 66: 2, 80: 2, 98: 2, 153: 2, 54: 2, 239: 2, 184: 2, 112: 2, 64: 2, 118: 2, 106: 2, 47: 2, 11: 2, 228: 2, 244: 2, 37: 2, 87: 2, 245: 2, 221: 2, 195: 2, 205: 2, 105: 2, 40: 2, 93: 2, 140: 2, 115: 2, 30: 2, 200: 2, 34: 2, 186: 2, 29: 2, 235: 2, 175: 2, 227: 2, 159: 2, 49: 2, 171: 2, 242: 2, 77: 2, 126: 2, 252: 2, 236: 2, 255: 2, 31: 2})
#count.most_common()
[(117, 4), (199, 2), (35, 2), (203, 2), (253, 2), (70, 2), (246, 2), (132, 2), (88, 2), (67, 2), (129, 2), (148, 2), (243, 2), (94, 2), (10, 2), (250, 2), (21, 2), (170, 2), (156, 2), (179, 2), (19, 2), (222, 2), (89, 2), (107, 2), (57, 2), (90, 2), (123, 2), (198, 2), (141, 2), (60, 2), (138, 2), (33, 2), (41, 2), (224, 2), (82, 2), (160, 2), (143, 2), (104, 2), (194, 2), (173, 2), (58, 2), (83, 2), (230, 2), (185, 2), (23, 2), (109, 2), (15, 2), (101, 2), (142, 2), (76, 2), (158, 2), (136, 2), (7, 2), (226, 2), (216, 2), (114, 2), (193, 2), (166, 2), (38, 2), (254, 2), (197, 2), (2, 2), (202, 2), (207, 2), (1, 2), (45, 2), (86, 2), (127, 2), (241, 2), (154, 2), (12, 2), (204, 2), (251, 2), (3, 2), (62, 2), (68, 2), (212, 2), (231, 2), (99, 2), (42, 2), (53, 2), (149, 2), (124, 2), (66, 2), (80, 2), (98, 2), (153, 2), (54, 2), (239, 2), (184, 2), (112, 2), (64, 2), (118, 2), (106, 2), (47, 2), (11, 2), (228, 2), (244, 2), (37, 2), (87, 2), (245, 2), (221, 2), (195, 2), (205, 2), (105, 2), (40, 2), (93, 2), (140, 2), (115, 2), (30, 2), (200, 2), (34, 2), (186, 2), (29, 2), (235, 2), (175, 2), (227, 2), (159, 2), (49, 2), (171, 2), (242, 2), (77, 2), (126, 2), (252, 2), (236, 2), (255, 2), (31, 2)]
#sorted(count.items())
[(1, 2), (2, 2), (3, 2), (7, 2), (10, 2), (11, 2), (12, 2), (15, 2), (19, 2), (21, 2), (23, 2), (29, 2), (30, 2), (31, 2), (33, 2), (34, 2), (35, 2), (37, 2), (38, 2), (40, 2), (41, 2), (42, 2), (45, 2), (47, 2), (49, 2), (53, 2), (54, 2), (57, 2), (58, 2), (60, 2), (62, 2), (64, 2), (66, 2), (67, 2), (68, 2), (70, 2), (76, 2), (77, 2), (80, 2), (82, 2), (83, 2), (86, 2), (87, 2), (88, 2), (89, 2), (90, 2), (93, 2), (94, 2), (98, 2), (99, 2), (101, 2), (104, 2), (105, 2), (106, 2), (107, 2), (109, 2), (112, 2), (114, 2), (115, 2), (117, 4), (118, 2), (123, 2), (124, 2), (126, 2), (127, 2), (129, 2), (132, 2), (136, 2), (138, 2), (140, 2), (141, 2), (142, 2), (143, 2), (148, 2), (149, 2), (153, 2), (154, 2), (156, 2), (158, 2), (159, 2), (160, 2), (166, 2), (170, 2), (171, 2), (173, 2), (175, 2), (179, 2), (184, 2), (185, 2), (186, 2), (193, 2), (194, 2), (195, 2), (197, 2), (198, 2), (199, 2), (200, 2), (202, 2), (203, 2), (204, 2), (205, 2), (207, 2), (212, 2), (216, 2), (221, 2), (222, 2), (224, 2), (226, 2), (227, 2), (228, 2), (230, 2), (231, 2), (235, 2), (236, 2), (239, 2), (241, 2), (242, 2), (243, 2), (244, 2), (245, 2), (246, 2), (250, 2), (251, 2), (252, 2), (253, 2), (254, 2), (255, 2)]
쓸만해진 것 같지만 most_common()의 출력이 아직 마음에 안든다. 이왕이면 같은 숫자면 정렬되어 있는게 더 마음에 들 것 같다.
이 경우에는 리스트를 미리 sort 해서 Counter로 바꿔주자
result.sort()
count=Counter(result)
print(count)
print(count.most_common())
delta_x : 255
Counter({117: 4, 1: 2, 2: 2, 3: 2, 7: 2, 10: 2, 11: 2, 12: 2, 15: 2, 19: 2, 21: 2, 23: 2, 29: 2, 30: 2, 31: 2, 33: 2, 34: 2, 35: 2, 37: 2, 38: 2, 40: 2, 41: 2, 42: 2, 45: 2, 47: 2, 49: 2, 53: 2, 54: 2, 57: 2, 58: 2, 60: 2, 62: 2, 64: 2, 66: 2, 67: 2, 68: 2, 70: 2, 76: 2, 77: 2, 80: 2, 82: 2, 83: 2, 86: 2, 87: 2, 88: 2, 89: 2, 90: 2, 93: 2, 94: 2, 98: 2, 99: 2, 101: 2, 104: 2, 105: 2, 106: 2, 107: 2, 109: 2, 112: 2, 114: 2, 115: 2, 118: 2, 123: 2, 124: 2, 126: 2, 127: 2, 129: 2, 132: 2, 136: 2, 138: 2, 140: 2, 141: 2, 142: 2, 143: 2, 148: 2, 149: 2, 153: 2, 154: 2, 156: 2, 158: 2, 159: 2, 160: 2, 166: 2, 170: 2, 171: 2, 173: 2, 175: 2, 179: 2, 184: 2, 185: 2, 186: 2, 193: 2, 194: 2, 195: 2, 197: 2, 198: 2, 199: 2, 200: 2, 202: 2, 203: 2, 204: 2, 205: 2, 207: 2, 212: 2, 216: 2, 221: 2, 222: 2, 224: 2, 226: 2, 227: 2, 228: 2, 230: 2, 231: 2, 235: 2, 236: 2, 239: 2, 241: 2, 242: 2, 243: 2, 244: 2, 245: 2, 246: 2, 250: 2, 251: 2, 252: 2, 253: 2, 254: 2, 255: 2})
[(117, 4), (1, 2), (2, 2), (3, 2), (7, 2), (10, 2), (11, 2), (12, 2), (15, 2), (19, 2), (21, 2), (23, 2), (29, 2), (30, 2), (31, 2), (33, 2), (34, 2), (35, 2), (37, 2), (38, 2), (40, 2), (41, 2), (42, 2), (45, 2), (47, 2), (49, 2), (53, 2), (54, 2), (57, 2), (58, 2), (60, 2), (62, 2), (64, 2), (66, 2), (67, 2), (68, 2), (70, 2), (76, 2), (77, 2), (80, 2), (82, 2), (83, 2), (86, 2), (87, 2), (88, 2), (89, 2), (90, 2), (93, 2), (94, 2), (98, 2), (99, 2), (101, 2), (104, 2), (105, 2), (106, 2), (107, 2), (109, 2), (112, 2), (114, 2), (115, 2), (118, 2), (123, 2), (124, 2), (126, 2), (127, 2), (129, 2), (132, 2), (136, 2), (138, 2), (140, 2), (141, 2), (142, 2), (143, 2), (148, 2), (149, 2), (153, 2), (154, 2), (156, 2), (158, 2), (159, 2), (160, 2), (166, 2), (170, 2), (171, 2), (173, 2), (175, 2), (179, 2), (184, 2), (185, 2), (186, 2), (193, 2), (194, 2), (195, 2), (197, 2), (198, 2), (199, 2), (200, 2), (202, 2), (203, 2), (204, 2), (205, 2), (207, 2), (212, 2), (216, 2), (221, 2), (222, 2), (224, 2), (226, 2), (227, 2), (228, 2), (230, 2), (231, 2), (235, 2), (236, 2), (239, 2), (241, 2), (242, 2), (243, 2), (244, 2), (245, 2), (246, 2), (250, 2), (251, 2), (252, 2), (253, 2), (254, 2), (255, 2)]
마음에 드는 결과가 나온 것 같다.
사실 이번 과제에서 필요했던 것은 item의 이름으로 즉 key로 분류한 경우이지만 찾아보고 해보면서 여러가지를 정리해봤다.
과제 결론
과제는 AES의 DDT에는 3개의 숫자밖에 나타나지 않고 그 피크의 차이도 작아서 DCA(Differential computation analysis) 즉 차분공격에 강하다는 점을 설명하기를 원했던 것 같다. 그 3개의 숫자를 찾기 위해 사용한 코드는 다음과 같다.
from collections import Counter
Sbox = (
0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16
)
for delta_x in range(0,0x100):
result=[]
for x in range (0,0x100):
result.append(Sbox[x]^Sbox[x^delta_x])
print(result)
print("delta_x : {}".format(delta_x))
count=Counter(result)
print(sorted(count.items()))
결과적으로 256,2,4의 3개의 값이 나왔다. 256은 입출력차이가 0 즉 입력에 차이가 없음 당연히 출력도 차이가없기때문에 0이라서 0,0에는 원래 모든 경우의 수가 있는 것이 맞아서 256
그 외에 차가 있을 경우에 대해서는 대부분이 2 일부가 4 로 큰 차이가 없기에 이론적으로 차분공격에 안전하다고 할 수 있다는 결론으로 레포트를 썼다.
참고로 이 DDT안의 값은 짝수일 수 밖에 없다.
a1^b = a2 a2^b = a1 이기 때문에 결국 2번씩 중복되기 때문이다.
쓰다보니 말투가 레포트체가 되어있었네요ㅋㅋㅋㅋㅋㅋㅋ