QR Code 복구記 2016-02-28 김민정 1
목차 1. 발표자소개 2. QR Code? 3. QR Code Encoding with 7 Section 4. QR Code Decoding with 7 Section 2
1. 발표자소개 3
프로필 이름소속군대주분야 김민정 ( 金珉廷 ) 충남대학교컴퓨터공학과 3학년, ARGOS, 블랙펄미필 ( 면제 ) 시스템, 리버싱, 코딩 주요경력 2014 Power of XX 최우수상 2015 소프트웨어개발보안경진대회최우수상 ( 장관상 ) 2015 전국정보보호동아리연합 KUCIS 영남 / 호남권역세미나발표 ( 개쩐다 ) 2015 전국정보보호동아리연합 KUCIS 우수프로젝트상우수상 ( 모바일브라우저퍼저 ) Lord of Sql Injection All Clear! (Top 18) 4
2. QR Code? 5
솔직히모르는사람없다 기업 정보전달 광고 CTF.. 6
손상된 QR Code 7
3. QR Code Encoding with 7 Section 8
0) Intro 1 Data Analysis 2 Data Encoding 3 Error Correction Coding 4 Structure Final Message 5 Module Placement in Matrix 6 Data Masking 인코딩모드선택인코딩 마스크패턴사용 7 Format and Version Information 오류복원코드생성 최종구조생성 QR code 행렬에배치 포맷및버전정보추가 9
1) Data Analysis - 4 가지의인코딩모드가있다 Numeric Alphanumeric Byte Kanji 0~9 0~9 대문자 특수문자일부 ($ % * + -. / : space) ISO-8859-1 (UTF-8) Shift JIS 10
1) Data Analysis - 제일효율적인모드는?? 201402326 Numeric mode HELLO WORLD HELLO WORLD!! ^_^ 乃凸 Alphaumeric mode Byte mode Kanji mode 11
2) Data Encoding - Step1 : 오류복원레벨선택 L M Q H 오류복원레벨 오류복원능력 데이터의 7% 복원데이터의 15% 복원데이터의 25% 복원데이터의 30% 복원 12
2) Data Encoding - Step2 : QR code 버전선택 13
2) Data Encoding - Step2 : QR code 버전선택 가장작은버전은어떻게결정할까! 14
2) Data Encoding - Step2 : QR code 버전선택 Character capacities table 1 버전 오류복원레벨 Numeric Mode Alphanumeric Mode Byte Mode L 41 25 17 10 M 34 20 14 8 Q 27 16 11 7 H 17 10 7 4 Kanji Mode 가장작은버전은어떻게결정할까! 15
2) Data Encoding - Step3 : 모드식별자추가 모드 Numeric Mode 0001 Alphanumeric Mode 0010 Byte Mode 0100 Kanji Mode 1000 모드식별자 16
2) Data Encoding - Step4 : 문자수식별자추가 HELLO WORLD - Alphanumeric Mode, Version1 9 bits 11 = 1011 = 000001011 - Step5 : 선택한모드로인코딩 17
2) Data Encoding - Step6 : 패딩추가 8 비트로나누어떨어지도록마지막에 0 을추가 패딩바이트추가 ( 11101100 00010001 ) 00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000 11101100 00010001 11101100 18
3) Error Correction Coding 4) Structure Final Message 19
5) Module Placement in Matrix - 기능패턴 Finder Pattern 양쪽위, 왼쪽아래 Separator Finder Pattern 주위 Alignment Pattern 버전2 이상 Timing Pattern Finder Pattern 연결 Dark Module 한개의검정색모듈 20
5) Module Placement in Matrix - 공간예약 Format Information Version Information ( 버전 7 이상 ) 21
5) Module Placement in Matrix - 데이터비트배치 22
6) Data Masking - 마스킹? 마스킹 흰색모듈은검정색모듈로, 검정색모듈은흰색모듈로변경해야하는것을의미한다. 즉, 마스킹은모듈의색을전환하는것이다. 23
6) Data Masking - 마스크패턴 Mask Number True일경우비트변환 0 (row + column) mod 2 == 0 1 (row) mod 2 == 0 2 (column) mod 3 == 0 마스크패턴1 : 모든짝수행은마스크된다. 마스크패턴2 : 모든세번째열이마스크된다. 기능패턴과예약영역은마스크하지않는다. 24
6) Data Masking - 최적의마스크패턴결정 네가지패널티규칙 행또는열에서 5개이상의같은색모듈그룹에대해패널티를준다. 같은색의 2*2 영역에대해패널티를준다. Finder Pattern과유사한패턴이있는경우큰패널티를준다. 검정색과흰색모듈비율의차이가많이날수록더큰패널티를준다. 25
7) Format and Version Information - Format String 오류복원레벨과마스크패턴번호를 5 비트로나타낸다. 오류복원레벨 L 01 M 00 Q 11 H 10 비트 오류복원레벨 L, 마스크패턴 4 를사용하면 01 100 이다. - Format String 에대한오류복원비트 10 개생성 26
7) Format and Version Information - Format String 27
7) Format and Version Information - Version Information 28
ㅠㅠ Break Time!! 29
ㅠㅠ Break Time!! 30
4. QR Code Decoding with 7 Section 31
0) Intro 1 Format and Version Information 2 Data Masking 3 Module Placement in Matrix 4 Structure Final Message 5 Error Correction Coding 6 Data Encoding 7 Data Analysis 32
1) Format and Version Information Format String 111110110101010 오류복원레벨 L, 마스크패턴 2 번 Version Information 25 * 25 : 버전 2 33
2) Data Masking Mask Pattern 2 (column) mode 3 == 0 34
2) Data Masking Mask Pattern 2 (column) mode 3 == 0 35
3) Module Placement in Matrix 36
3) Module Placement in Matrix 37
4) Structure Final Message 38
5) Error Correction Coding 오류복원레벨 L 최대 7% 의손실된데이터복구가능! 현재약 13% 손실 39
6) Data Encoding 00010010 : 18 Character 0100 Byte mode 40
6) Data Encoding Byte Mode Encoding Ex) HELLO WORLD (1) 문자를 16 진수로변환 HELLO WORLD -> 0x48 0x65 0x6c 0x6c 0x6f 0x20 (2) 각바이트를 8 비트의이진수로변환 H -> 0x48 -> 01001000 E -> 0x65 -> 01100101 41
6) Data Encoding 0100 Byte Mode 00010010 18 Characters 42
6) Data Encoding 0100 Byte Mode 00010010 18 Characters 01001000 H 01100101 e 01101100 l 01101100 l 01101111 o 00100000 01001000 H 01100001 a 01100011 c 01101011 k 01000011 C 01100001 a 01101101 m 01110000 p 01111110 ~ 00100000 00111010 : 0010?0?1 ) <- guessing 43
6) Data Encoding 18 Character = 144 bits 144 bits + 4 bits + 8 bits = 156 bits 156 mod 8 = 4 0100 Byte Mode 00010010 18 Characters 01001000 H 01100101 e 01101100 l 01101100 l 01101111 o 00100000 01001000 H 01100001 a 01100011 c 01101011 k 01000011 C 01100001 a 01101101 m 01110000 p 01111110 ~ 00100000 00111010 : 0010?0?1 ) <- guessing 0000 for 8 bit 44
6) Data Encoding 11101100 00010001 padding 45
+) another QR Code 46
+) another QR Code 25 * 25 : 버전 2 Format String 011011010 010111011011010 오류복원레벨 Q, 마스크패턴 6 번 47
+) another QR Code 25 * 25 : 버전 2 Format String 011011010 010111011011010 오류복원레벨 Q, 마스크패턴 6 번 15% 의데이터를복구할수있다! 약 60% 데이터손실 48
+) another QR Code Mask Pattern 6 ( ((row * column) mod 2) + ((row * column) mod 3) ) mod 2 == 0 49
+) another QR Code Mask Pattern 6 ( ((row * column) mod 2) + ((row * column) mod 3) ) mod 2 == 0 50
+) another QR Code 000010100 : 20 0010 Alphanumeric mode 51
+) another QR Code Alphanumeric Mode Encoding Ex) HELLO WORLD (1) 두개씩나눈다. HE, LL, O, WO, RL, D (2) 각쌍들에대한이진수를생성한다. ( 11비트 ) H(17), E(14), (45*17)+14=779 -> 01100001011 52
+) another QR Code 0010 Alphanumeric Mode 000010100 20 Characters 01010111000 FL 00111010010 AG 11011100110 I 1010001000? S 29 Character = (29/2 + 29%2) * 11 bits = 165 bits -> 176 bits 20 Characters = 11 bits * 10 pairs = 110 bits 110 + 4 + 9 = 123 bits 53
+) another QR Code 00100000 10100010 10111000 00111010 01011011 10011010 10001000 ( 64 bits missing )??000000 padding 11101100 00010001 54
+) another QR Code reedsolomon 라이브러리사용!! 55
+) another QR Code FLAG IS G+JQAH:FW3X 56
QR Code 복구記 QnA 그렇구나. 57