Cryptography and Network Security Chapter 6. Multiple Encryption & DES clear a replacement for DES was needed  theoretical attacks that can break it.

Presentation on theme: "Cryptography and Network Security Chapter 6. Multiple Encryption & DES clear a replacement for DES was needed  theoretical attacks that can break it."— Presentation transcript:

1 Cryptography and Network Security Chapter 6

2 Multiple Encryption & DES clear a replacement for DES was needed  theoretical attacks that can break it  demonstrated exhaustive key search attacks AES is a new cipher alternative prior to this alternative was to use multiple encryption with DES implementations Triple-DES is the chosen form 2

3 Double-DES could use 2 DES encrypts on each block  C = E(K 2,E(K 1,P))  P = D(K 1,D(K 2,C))  우리의 예상은 56x2 = 112bit 의 Key Size. issue of reduction to single stage  E(K 2,E(K 1,P)) = E(K 3,P) -------- (6.1)  (6.1) 과 같은 식에서 K 3 가 존재한다고 가정  만약 위의 가정이 사실이라면 56bit 를 이용한 단일키  위의 가정이 틀리면 단일 DES 의 단일 적용에 정의되지 않 는 다수의 사상 중 하나를 생성하게 될 것이라는 것은 타 당 [CAMP92] 3

4 “Meet-In-The-Middle” Attack works whenever use a cipher twice since X = E(K 1,P) = D(K 2,C) attack by encrypting P with all keys and store then decrypt C with keys and match X value can show takes O(2 56 ) steps  얼핏 보기에, 이중 DES 는 키를 탐색하 기 위한 탐색 횟수가 2 56 번 ( 하나의 DES 에 대응 ) 에서 2 112 번 ( 두 개의 DES 에 대응 ) 으로 증가하는 것처럼 보임  그러나 중간 일치 공격과 같은 기지 평 문공격을 사용하면 2 112 가 아닌 2 56 으 로 약간의 향상만이 있을 뿐임을 증명 이중 DES 에 대한 중간일치공격 중간 일치 공격에 대한 표 4

5 Triple-DES with Two-Keys hence must use 3 encryptions  would seem to need 3 distinct keys but can use 2 keys with E-D-E sequence  C = E(K 1,D(K 2,E(K 1 (P)))  P = D(K 1,E(K 2,D(K 1 (C)))  if K1=K2 then can work with single DES(!) standardized in ANSI X9.17 & ISO8732( 키 관리 표준 ) no current known practical attacks  [COPP94] 는 3 중 DES 에 대한 전사적 공격은 2 112 ~5x10 33 의 차수로, 차분 암호 해독은 지수적 증가 (!) 로 추정되며 단일 DES 와 비교해 서 10 52 이 넘는다.  several proposed impractical attacks might become basis of future attacks 5

6 몇 가지 제안된 공격... 선택 평문 공격 [MERK81]  Fig6.1b 의 A=0 의 첫번째 중간 값을 생성하는 평문 값을 찾은 다음, 두 개의 키를 찾기 위 해 중간 결과에 의한 공격을 사용  암호해독의 복잡도는 2 56, 이 기법은 현실적으 로 2 56 개의 선택 평문 - 암호 쌍이 요구 기지평문 공격 [VANO90]  MERK81 을 개선, 그러나 복잡도는 더 높음  만약 A,C(Fig6.1b) 를 알면 2DES 로 축소될 수 있다는 관찰에 근거  공격자는 A 의 가능한 값을 선택할 수 있고, 그렇게 되면 A 를 생성하는 기지의 (P,C) 쌍을 찾게 됨  간단한 공격방법 [ 자세한 것은 논문참조 ]  n 개의 (P,C) 를 구함. 6.2b 의 표 작성  임의의 a 선택. 6.2c 표 작성 P = D(i,a), B = D(i,C)  i 번째 후보 값이 구해지면 i+1 번째 수행 하여 j 값을 구한다  각 후보 키 쌍 (i,j) 를 테스트 6

7 Triple-DES with Three-Keys although are no practical attacks on two-key Triple-DES have some indications can use Triple-DES with Three-Keys to avoid even these  C = E(K 3,D(K 2,E(K 1,P))) has been adopted by some Internet applications, eg PGP, S/MIME(in ch18) 7

8 Modes of Operation block ciphers encrypt fixed size blocks  eg. DES encrypts 64-bit blocks with 56-bit key need some way to en/decrypt arbitrary amounts of data in practise NIST SP 800-38A defines 5 modes have block and stream modes to cover a wide variety of applications can be used with any block cipher 운영모드 8

9 Electronic Codebook Book (ECB) message is broken into independent blocks which are encrypted each block is a value which is substituted, like a codebook, hence name each block is encoded independently of the other blocks  C i = E(K,P i ) uses: secure transmission of single values 9

10 Advantages and Limitations of ECB message repetitions may show in ciphertext  if aligned with message block  particularly with data such graphics  or with messages that change very little, which become a code-book analysis problem weakness is due to the encrypted message blocks being independent 동일한 메시지가 반복되면 암호문도 동일하게 나오는 문제점이 있다 main use is sending a few blocks of data  DES, AES 키 전송에 사용 10

11 Cipher Block Chaining (CBC) message is broken into blocks linked together in encryption operation each previous cipher blocks is chained with current plaintext block, hence name use Initial Vector (IV) to start process  C i = E(K,[P i XOR C i -1])  C -1 = IV uses: bulk data encryption, authentication 11

12 Message Padding at end of message must handle a possible last short block  which is not as large as blocksize of cipher  pad either with known non-data value (eg nulls)  or pad last block along with count of pad size  eg. [ b1 b2 b3 0 0 0 0 5]  means have 3 data bytes, then 5 bytes pad+count  this may require an extra entire block over those in message there are other, more esoteric modes, which avoid the need for an extra block 12

13 Advantages and Limitations of CBC a ciphertext block depends on all blocks before it any change to a block affects all following ciphertext blocks need Initialization Vector (IV)  which must be known to sender & receiver  if sent in clear, attacker can change bits of first block, and change IV to compensate  hence IV must either be a fixed value (as in EFTPOS)  or must be sent encrypted in ECB mode before rest of message  IV 선택에 대한 권고  동일한 암호화 키  난수 13

14 Stream Modes of Operation block modes encrypt entire block may need to operate on smaller units  real time data convert block cipher into stream cipher  cipher feedback (CFB) mode  output feedback (OFB) mode  counter (CTR) mode use block cipher as some form of pseudo-random number generator 14

15 Cipher FeedBack (CFB) message is treated as a stream of bits added to the output of the block cipher result is feed back for next stage (hence name) standard allows any number of bit (1,8, 64 or 128 etc) to be feed back  denoted CFB-1, CFB-8, CFB-64, CFB-128 etc most efficient to use all bits in block (64 or 128)  C i = P i XOR E(K,C i -1)  C -1 = IV uses: stream data encryption, authentication 15

16 Advantages and Limitations of CFB appropriate when data arrives in bits/bytes most common stream mode limitation is need to stall while do block encryption after every n-bits note that the block cipher is used in encryption mode at both ends errors propogate for several blocks after the error 16

17 Output FeedBack (OFB) message is treated as a stream of bits output of cipher is added to message output is then feed back (hence name) feedback is independent of message can be computed in advance  O i = EK(O i-1 )  C i = P i XOR O i  O -1 = IV uses: stream encryption on noisy channels 17

18 Advantages and Limitations of OFB needs an IV which is unique for each use  if ever reuse attacker can recover outputs bit errors do not propagate more vulnerable to message stream modification sender & receiver must remain in sync only use with full block feedback  subsequent research has shown that only full block feedback (ie CFB-64 or CFB-128) should ever be used 18

19 Counter (CTR) a “new” mode, though proposed early on similar to OFB but encrypts counter value rather than any feedback value must have a different key & counter value for every plaintext block (never reused)  O i = E(K,i)  C i = P i XOR O i uses: high-speed network encryptions 19

20 Advantages and Limitations of CTR efficiency  can do parallel encryptions in h/w or s/w  can preprocess in advance of need  good for bursty high speed links random access to encrypted data blocks provable security (good as other modes) but must ensure never reuse key/counter values, otherwise could break (cf OFB) 20

21 XTS-AES Mode new mode, for block oriented storage use  in IEEE Std 1619-2007 concept of tweakable block cipher different requirements to transmitted data uses AES twice for each block  T j = EK2(i) XOR α j  C j = EK1(P j XOR T j ) XOR T j  where i is tweak & j is sector no each sector may have multiple blocks 21

22 암호저장화 요구 사항 1. 암호문은 자유롭게 공격자로부터 이용이 가능하다. 2. 데이터 레이아웃은 저장 매체에서 혹은 전송 중에 변경 되지 않고, 평문 데이터와 크기가 같다 3. 비순차적 접근을 허용한다. 4. 암호문은 16 바이트의 배수로 이루어진다 5. 데이터 블럭의 위치를 제외하곤, 메타데이터는 사용되 지 않는다. 6. 동일한 위치에 쓰여질 때는 동일한 암호문이 된다 7. 표준에 준수한 장치들은 다른 표준의 장치에 의해 암호 화된 데이터를 복호화하기 위해 구성될 수 있다 22

23 XTS-AES Mode Per block XTS-AES 파라미터  P j : J 번째 평문 블록. 마지막 블럭을 제외하곤 모두 128 비트.  C j : j 번째 암호문 블럭. 마지막 블럭을 제외 하곤 모두 128 비트  j : 블럭의 순차 번호 (CTR 모드의 계수와 동일 )  i : 128 비트의 변경 값. 연속적으로 할당되고 임의의 양의 정수로부터 시작.( 난수에 해당 )  a : 다항식 x 에 대응하는 원시원소  a j : a 를 j 번 곱한것  ⊕ : 비트 XOR 연산  ⊗ : GF 위에서 곱셈  T = E(K 2,i) ⊗ a j  PP = P ⊕ T // CC = C ⊕ T  CC = E(K 1,PP) // PP = D(K 1,CC)  C = CC ⊕ T // P = PP ⊕ T 암호화 : C = CC ⊕ T = E(K 1,PP) ⊕ T = E(K 1,P ⊕ T) ⊕ T 복호화 : P = PP ⊕ T = D(K 1, CC) ⊕ T = D(K 1,C ⊕ T) ⊕ T 23

24 섹터에 대한 운용 섹터에 대한 단위는 128 비트 블럭으로 구성  마지막 블럭은 NULL, 1~127 비트로 채워짐 각 블록의 암호화는 독립적으로 진행  단, 128 블럭보다 작을 때 ciphertext-stealing 기술 사용 CTR 모드에서 볼 수 있듯이, XTS-AES 모드도 병렬 운 용에 적합하다고 할 수 있음  체이닝 구조가 아니기 때문에 동시에 여러 블럭이 암호화 또는 병렬화 가능 24

25 Advantages and Limitations of XTS-AES efficiency  can do parallel encryptions in h/w or s/w  random access to encrypted data blocks has both nonce & counter addresses security concerned related to stored data 25

26 Summary Multiple Encryption & Triple-DES Modes of Operation  ECB, CBC, CFB, OFB, CTR, XTS-AES 26