티스토리 툴바


실제 대부분의 QR 코드 문제들은

알려진 QR코드 디코더에 간단히 사진을 입력하면 

안에 인코딩 되어있는 정보가 나오는 수준에 국한 되어있지만


Codegate 2011년 문제를 보면 예외 적으로 QR코드를 적당히 손상시켜

의도적으로 디코딩 되지 않는 문제를 접하게 됩니다.


이를 계기로 ISO/IEC 스탠다드 문서(http://raidenii.net/files/datasheets/misc/qr_code.pdf)

를 참고로 해킹대회에 나올만한 QR문제 유형을 QR코드 인코딩/디코딩방식과 함께 간략하게 살펴 보겠습니다.


먼저 QR코드는 말그대로 Quick Record 라는 이름처럼 빠르게 인코딩/디코딩을 해서 정보를 읽어내야 하기때문에

알고리즘 생성 과정에서 찢어짐/부분손상/뒤틀림 등의 여러가지 발생할 수 있는 가짓수를 고려해 자체적으로 부분 재생할수 있는 알고리즘이 사용됩니다.


간단한 예로, 2D의 QR코드가 3D의 그림에 삽입 되어 있는 경우에도

이 2D의 QR코드의 인코딩된 정보를 읽곤 합니다. 

(마트에서 QR 코드 인식기기를 찍을때 보통 여러가지 각도에서 찍는것도 하나의 예)


거두 절미 하고 일단 QR코드가 어떻게 생성되는지 간단하게 살펴 봅시다.

 

QR코드는 일정한 크기의 보드바탕에 흑/백의 네모 배열들의 조합으로 만들어집니다. 각각의 보드 사이즈를 '버젼'이라 일컫는데 버젼1부터 버젼 40이 존재하며 각각의 버젼은 17+(4x)  by 17+(4x)의  (x는 버젼명)사이즈를 가집니다. 즉 버젼1은 21x21. 버젼 2는 25x25가 되는거죠. 이버젼에는 또한 find pattern, format information, version information, encoded information등이 들어가게 되는데 이것들이 바로 우리가 보게되는 흑/백 네모 배열의 조합들 입니다.


Find Pattern - 오른쪽/왼쪽 상단 ,  그리고 왼쪽 하단 귀퉁이의 3 by 3, 5 by 5, 7 by 7 의 상자로 둘러싸져 있는 큰 네모박스들


Format Information - QR 코드의 자세한 인코딩 정보를 담고있는 일종의 헤더와같은 영역. 아래 그림 참조


Version Information - QR코드 보드 크기의 사이즈, 즉 버젼 정보를 담고 있는 영역


Timing Belt - 모든 QR코드에 항상 같은위치에 같은 식별 패턴이 공통적으로 들어 가게 되는 요소. 아래 그림 참조


Alignment Pattern - 배열 패턴. 실제로 Find Pattern 을 제외한 상대적으로 크기가 작은 네모들. 이 패턴들은 QR코드가


보드에 인코딩 될때 일정하게 배열 되도록 패턴을 잡도록 도와 주는 부분들 입니다.


Encoded Information - 위의 요소들을 제외한 QR코드의 모든 부분들





위의 언급된 각각의 QR코드 요소들은 모두 BCH알고리즘에 의해 생성됩니다. BCH 알고리즘에 대해 간단하게 예를들어 보죠


HELLO WORLD 라는 내용을 담은 버젼1(21 by 21)의 QR 코드를 예로 들겟습니다. 참고로 QR코드는, 숫자, alphanumeric value, 유니코드, 간지체 (일본어, QR코드가 일본에들에 의해 만들어 졌습니다.) 등 담는 정보에 다라 인코딩 룰이 달라지며,  각기다른 방식의 인풋들도 함께 사용 될수 있습니다.

(ex, 일본어 + 영어..)


일단 Hello World라는 인코딩할 메시지를 이진수로 변환해야 하는데요. 단순한 아스키코드로의 일대일 대응이 아니라 다음과 같은

방법을 사용합니다. 먼저 Hello World를 2 캐릭터씩 쪼개서 아래와 같이 변환합니다.


(QR코드에서 사용하는 알파벳의 숫자 대응코드 http://www.thonky.com/qr-code-tutorial/alphanumeric-table/)


HE 같은 경우  45*17 + 14 = 779가 되는거죠. 45진수의 개념으로 생각하시면 됩니다. 이걸이제 이진수로 변환하면 

01100001011이 됩니다 나머지도 LL , O%20(공백) , WO, RL, D와 같이 쪼개어 마찬가지도 변환해주시면 됩니다.  만약 두자리씪 쪼개어 끝에 한문자가 남게된다면 앞에 0을 붙여 6bit의 스트링을 만듭니다 (이경우엔 D가 남게되니 , D=13, 001101)


또한 인코딩할 데이터의 앞에는 인코딩 정보라는 시그니쳐와 인코딩 정보 길이를 알려주는 일종의 헤더가 들어가게됩니다.

시그니쳐는 0010 이며 인코딩하는 정보의 종류에따라 앞에 0 패딩값을 부쳐 다음과 같이 표기합니다.

0010 (시그니쳐) 00000(패딩)1011(길이) 

Versions 1 through 9

  • Numeric mode: 10 bits
  • Alphanumeric mode: 9 bits
  • Binary mode: 8 bits
  • Japanese mode: 8 bits

(버젼 1-9에 해당하는 인코딩 룰. 

예를들어 버젼 3의 숫자만을 포함하는 방식을 선택 한다고 했을때

인코딩 헤더는 10bit의 길이를 가지며, 그 10bit의 값은 실제 인코딩할 문자/숫자/또는 둘다의 갯수를 표현합니다.)




이런식으로 인코딩하여 일렬로 나란히 붙이게 되면 최종적으로 아래의 값을 얻게 됩니다.

0010 0000010110110000101101111000110100010111001011011100010011010100001101

 

이외에도 각각 버젼에따라 최소한으로 가져야할 인코딩 부분의 길이가 존재하며

이 부분들을 보정하기 위해서 패딩 패턴을 사용하게 되며 여러가지 세심한 과정을 거치게 됩니다. 

(http://www.thonky.com/qr-code-tutorial/) 나머지 자세한 과정은 이사이트를 참조.



(아래설명은 위 사이트를 봣다는 전제하에 진행 / 사실 QR코드 생성 과정은 생략 해도 문제 풀이를 위해 )


위와 같이 인코딩 한 정보를 또 버젼에맞게 패딩을 붙이고, BCH 오류 보정 알고리즘을 통해 일종의 체크섬을

붙이게 되면 최종적으로 인코딩할 정보의 QR식 바이너리 형태의 값을 가지게 됩니다. (이런 복잡한 알고리즘을 체택하는 이유는, 뒤에도 설명되겠지만 QR코드 생성시 흑/백색깔의 뭉침, 읽는 속도향상/ 알고리즘의 무결점/ 등등을위해 선행됩니다)


제목 없음.png 



자 위 그림을 참조하면 이제 인코딩된 바이너리 정보를 제외하고 보다시피

timing belt, find pattern, 그리고 format information (+ version information , 버젼6이상에는 이 정보또한 기록됩니다)

어떠한 QR코드에나 관계없이 버젼별로 동일한 위치에 포함 되어 있습니다. 위그림은 버젼 1, 버젼2에 해당



이정도들이 잘못된다면 QR 코드값이 제대로 읽히지 않는거죠.

여기들어가는 값들또한 마찬가지로 BCH알고리즘을 통해서 들어가는데 복잡한 계산(BCH 알고리즘)임으로

아래의 테이블을 참조해봅시다.


제목 없음.png

테이블에 주어진 값은 ECC level, mask pattern, 그리고 type information입니다. ECC level과 mask pattern은 간략하게 설명해서 QR CODE가 손상 됫을때 회복할수 잇는 정도 (ECC level) , 가독성을 높이기 위해 사용되는 패턴 (mask pattern)이라고 볼수있는데요. 그옆의 type information은 QR 코드가 사용하는 ECC level과 마스트패턴에 의해 BTC알고리즘을 통해 결정됩니다.


ECC Level은 문제에서 보다싶이 L, M, Q ,H가 잇는데요 각각 Low, Medium, Quality, High를 나타냅니다.

이 정도에 따라 QR코드가 회손됫을때 전체 크기의 몇퍼센트에 해당하는 값이 재생 될 수 있는지를 나타냅니다.


마찬가지로 Mask Pattern은

흑/백의 비율, 흑/백픽셀들이 일렬로 발생하는 횟수, 흑/백픽셀들이 2x2 사각형안에 뭉쳐있는 횟수등을 조정 하는데요

이를 토대로 "가독성"이 계산합니다. 그리고 이 계산된 "가독성"이 제일 좋은 Mask Pattern을 사용하여 실제 정보가 

QR 보드에 입력되게 되는 겁니다.


간단하게 요약하면 

계산된 type information이 올바른 값을 가지지 않는경우 (테이블에 명시되어 있는 값들중 하나)

그 QR CODE는 올바르지 않는 QR code로 인식되어 값이 읽히지 않는다는 것입니다.



제목 없음.png



이중요한 type information은 똑같은 정보가 위와같은 포지션에 2번 들어가게 되는데요 

15자리의 이값은 맨왼쪽 most significant bit 14번 비트부터 왼쪽 상단에 왼쪽부터 오른쪽으로

아래에서 위로 한번 입력되게 되고 마찬가지로 중앙 하단에서부터 아래에서 위로 그리고 우측 상단에 잇는곳으로 왼쪾에서 오른쪽으로 입력되게됩니다.

(참고로 1은 블랙, 0은 흰색)


Codegate 2011 issue300문제의 QR코드 같은경우 그림에서 볼수 있듯이 001100111010011의 type information 값을 가집니다. 이값이 바로 위의 테이블 어디에서도 볼수없는 잘못된 값이기때문에 오류가 뜨는것이죠

                                                <문제에서 주어진 QR코드>

제목 없음.png 



실제로 PPP의 codegate 2011 writeup과 leetmore 의 writeup을 참고해본 결과

각각 아래과 같은 type information으로 수정하여 답을 얻은 것을 알수있습니다.

제목 없음.png



두 QR코드와 원문 QR코드를 비교해봣을시 달라진 점은 format information입니다.

두팀 모두 서로다른 format information을 사용햇는데 두 format information 모두 형태가 적법한 문법에 맞는 표현이므로 

실제 인코딩된 값이 읽히게 되는 것입니다.



( QR의 format information은 위에서 언급된 ECC level과 mask pattern에 의해서 결정됩니다. 

먼저 ecc level은 정보의 훼손 정도를 고려해 사용자가 임의로 설정될수 있는 값입니다. 사용자는 선택된 ecc level과 인코딩 input을 가지고 QR 알고리즘의 페널티 부여 방식, 또는 위의 언급된 표현을 빌리자면 '가독성'을 가장 높이는 mask pattern을 결과적으로 체택 하게 되는 것입니다. 하지만 프로그램/알고리즘 내부적으로는 어느 mask pattern 이 최고의 가독성을 내는지는 먼저 그 마스크 패턴에 따라 QR코드를 설계한후 페널티를 각각 계산해 보아야 알 수 있습 니다. 이와 같은 성질때문에, 실제로 최적화된 mask pattern이 아닐지라도 값은 읽히게 되는것 입니다.)



mask pattern은 QR 알고리즘의 페널티 부여방식을 통해 , 최적화된 마스크 패턴을 쓰도록 전체 알고리즘이 설계되어 잇지만 가독성(여기서 가독성은 읽기 쉬운 정도가아닌 코드가 기기로 읽히냐 안 읽히냐의 여부/정도)을 최선으로 여기는 QR코드의 특성상 어떤 mask pattern을 사용해도 결과적으론 인코딩된 정보가 읽힙니다. )


실제로 PPP팀의 writeup을 읽어보면 이팀은 두가지 방식으로 답을 구하 였는데요.

GIMP를 통해 손수 QR코드를 수정해준 방법 이 외에도 QR코드를 인식하는 라이브러리를 조금 수정하여 답을 도출 했다고

나와 있는데요. 아마 위와 같은 최적 mask pattern 방식을 고려 하지 않고 인코딩된 정보만 우선적으로 읽도록 조금 수정하지 않앗나 싶습니다.




끝으로 긴글을 통해 요약해보면 


QR코드와 관련된 대부분읜 문제들은 인코딩된 정보가 손쉽게 알려진 디코더를 통해 구해질수 있다는 점과


만약 값이 읽히지 않을시 훼손 여부를 알아 낼 수있는 3가지요소 format information / timing belt / version information (6이상의 QR버젼을 쓸경우) 를 판별 해보는것이 문제 해결을 위해 키포인트 라는 것입니다.


이를통해 만약 출제자가


문제를 좀더 꼬아서 낼려 할시 format informatino 훼손과 더불어 version information까지 조작 할 경우를 들수 있겠습니다.

또한, 위 세가지 판별 요소만 만족될시에 정보가 쉽게 읽힌다는 점을 고려하면 쉘코드를 QR 코드 내부에 삽입하는것도 가능하겠습니다. 이점에 대해서는 곧 프로그램을 짜서 올리겠습니다.



p.s. ) 참조문서

http://raidenii.net/files/datasheets/misc/qr_code.pdf

http://www.thonky.com/qr-code-tutorial/

http://ppp.cylab.cmu.edu/wordpress/wp-content/uploads/2011/03/Codegate2011PQ-Writeup-PPP.pdf

http://leetmore.ctf.su/wp/codegate-yut-2011-forensic-300issue-300/

저작자 표시
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by luxs1t