New authentication algorithem likes OTP

invalid-file

알고리즘 : 옥민수
설계자 : 옥민수
코딩자 : 옥민수
기타등등 : 옥민수..
결국 원맨쇼..ㅋㅋ
e-mail : niceminsu@gmail.com
blog : blindlibrary.tistory.com




예전에 WOC 행사에서 이희승(멘토)님과 김참이(멘티)님께서 진행하신 OTP프로젝트를 보고

한번 만들어 볼까 하고 생각했었습니다. 왜 지금에서야 만드냐고 물으시면 슬픕니다,.

OTP의 장점인 인스턴스 패스워드는 좋긴 하지만 매우 불편합니다.

OTP생성기를 따로둬서 생성해야 하고 또 OTP생성기 역시 안전하다고 할 수는 없거든요..

그래서 기존의 방식대로 ID와 고정된 Password 만을 가지고 로그인 하는데 다만 전송되는 패스워드 메시지만

그때 그때 달라지는 방식을 구현해 봤습니다. 물론 전송되는 메시지에서 패스워드를 추출하는건 불가능합니다.

암호화가 아니라 패스워드 인증을 위해서 키를 생성하는거니 패스워드를 모르면 키에서 패스워드를 추출하는건

불가능합니다. 한마디로 복호화 할 필요가 없으니 추출 불가능하게 키를 생성해도 상관 없는거죠..

에에.. 나머지는 제가 그린 몇가지 그림과 코드를 훑어보시고 밑에 적을 설명서를 읽어보시면

잘 알게 되실겁니다. 코드이용에 관한 주의사항은 코드안에 들어있습니다. 한글로 되어있어요..

영어가 안되서..;;(현재 배우고 있..)

에.. 제가 이름붙이기로는 '로즈마리' 라고 이름을 붙였는데 아직은 가칭입니다. 혹은 로또같다고 해서

로또 프로젝트라고 붙여볼까도 생각중입니다. 만.. 만들었더니 필요없더라 하면..ㅋㅋ

일단 자바코드로 구현했고. 잘 돌아갑니다. 이클립스 프로젝트를 압축했습니다. 거의 대부분 자바 하시는

분들이 이클립스 쓰시니 불편함은 없을겁니다. IDE 딴거 쓰시거나 오로지 텍스트파일로.. 라고 하시면

코드 뽑아 쓰시면 되겠죠.. 에.. 테스트를 위해 메인 함수도 넣어놨는데 그냥 패스워드 받고 생성된

키를 출력해줄 뿐입니다.

그러면 설명 하겠습니다. 일단 그림을 봐주세요.

그냥 예전에 하던데로 쓰면 된다는걸 표현하고 있습니다.(알아요. 그림 못그리는거) 특히 웹에서 강력할 수 있습니다.

알고리즘이 대강 어떻게 흘러가는가를 표현하고 있습니다. 여기 안 들어 있지만 위에것들외에 추가로 몇개가 들어가 있습니다.

역시 서버와 유저 사이에 일어나는 일을 그리고 있습니다.

에.. 그러면 본격적으로 설명을 하겠습니다.
정확한 건 코드를 참고해 주셔도 감사하겠습니다.

아. 비트에 거부감을 가지시면 못 보실 수 도 있습니다. 또한 비트 논리연산에 거부감을 가지시는 분들도 보기 힘드실 수 있습니다.

기본적으로 유니코드를 기반으로 하고 있습니다. 아스키를 써도 되요,.. 그러면 최소 1자리에서 최대 60 자리가 되겠지요..

유니코드를 기반으로 하고 있기 때문에 거의 모든 연산은 2byte단위로 일어납니다. 알아두세요. 참고로 자바에서 char가 2byte 이기 때문에 유니코드를 기반으로 한건 아닙니다.(아니에요.. 절대 아니에요..)

먼저 패스워드는 1자 이상 30자 이하여야 합니다 혹은 최대 31자 까지 할 수 있습니다.(30자인 이유는 나중에 나옵니다.)

먼저 서버에서 공개용 키를 생성하는 방법인데요. 사실은 상관없을것 같습니다만 저는 제 나름대로 값을 크게 불리기 위해서 난수를 두번 생성합니다.
 
16비트중에서 처음 3비트 따로 난수를 생성하고 그 다음에 나머지 13비트의 난수를 생성해서 서로 OR연산을 합니다. 이때 앞의 3비트의 값이 0이 되지 않도록 합니다. 그러면 큰 값이 생성되게 됩니다. 지금와서 생각해 보니 왜 그랬을까 하는 생각도 듭니다. 뭔가 만들기 시작할 당시에는 이유가 있었던거 같은데.//.

이 값을 클라이언트에 전송합니다. 서버에서는 개별 클라이언트를 따로 인식할 수 있는 공간이면 어디건 값을 저장해도 괜찮습니다. 혹은 클라이언트에서 전송되어저 오는 값에 난수를 포함해도 상관없습니다. 어차피 공개하는 값이니까요.

그러면 클라이언트는 이 값을 받아서 유저로 부터 받은 오리지널 패스워드와 서버로부터 받은 2byte의 값을 가지고 패스워드 대체 키를 만들어 냅니다. 총 16byte의 일회용 키가 생성됩니다.

지금부터 이 값을 어떻게 생성하는지 설명하겠습니다.

먼저 패스워드 각 캐릭터(2byte)의 비트를 재 정렬 합니다. 저는 앞에서부터 홀수비트는 왼쪽 짝수비트는 오른쪽으로 정렬했습니다. 왜 이렇개 해야 하냐면 영어를 예로 들면 아스키코드를 그대로 씁니다. 제가 알고 있기로 유니코드는 하위 호환을 위해 아스키코드에다 앞의 비트를 붙인겁니다. 틀리다면 열심히 지적해 주세요.
 
결국 숫자가 작아지는 결과를 초래합니다. 또한 수치의 범위가 정해져 버립니다.  특정 언어만 쓴다고 가정하거나 기존의 패스워드가 아스키 방식이니 기존걸 그대로 쓴다고 가정하면 수치 범위가 정해지는 약점과 앞의 8bit가 거의 0이 되어버리는 현상이 발생할 수 있습니다. 그걸 방지하고자 비트를 분산시킵니다.

이렇게 비트를 바꿔놓은 후에는 이제 패스워드의 입력 순서를 검증해야 합니다. '바보나라'와 '보바나라'가 같을 수 없지 않습니까.. 이건 각 캐릭터를 XOR 하는것으로 해결합니다. 물론 XOR만 하면 안됩니다. XOR연산 결과에 다음 캐릭터를 더해줍니다. 그리고 다시 XOR합니다. x = pw[0]; x += pw[1]; x ^= pw[1]; 이런식으로 구현했습니다. 이러면 패스워드 순서를 보장해 줄 수 있는 2byte값이 생성됩니다. 이 값에다가 마지막으로 서버에서 받은 키값을 XOR헤줍니다./. 이것 역시 덧셈 포함해서요..

이제 실제 전송용 코드를 생성해 내는 방법을 설명 드립니다.

기본 원리는 이렇습니다.(X = 앞서 얻은 순서검증 값, Ax = 패스워드, Sx =  계산되어 나온 값)

          A1     A2        A3        A4        A5        A6  ···
xor      X    S1+A1   S2+A2   S3+A3   S4+A4   S5+A5 ···
───────────────────────────
          S1     S2        S3        S4        S5        S6

이게 기본 원리입니다.. 아리송 하시죠? 이걸가지고 키를 만든다고해서 키를 추출 못할리 없기때문입니다.

몇번 키 캡쳐해서 경우의수 연산하면 패스워드를 특정할 수 있을겁니다.

하지만 이건 말 그대로 기본원리이고,, 여기에 두가지 정도가 더 들어가서 추출 불가능하게 만들어 집니다.
에.. 어떻게 하냐하면.. 루프와 추가를 합니다. 에에.. 바뀐게 이렇습니다. A6까지만 있다고 가정하고

loop{
          A1(S1)      A2        A3        A4        A5        A6                
xor      X(S7+X)  S1+A1   S2+A2   S3+A3   S4+A4   S5+A5   S1+S6   ···
────────────────────────────────
             S1         S2        S3        S4        S5        S6        S7
}

이런식으로 루프할때마다 값이 추가가 됩니다. 첫째 자리의 괄호안에 있는 건 두번째 이상의 루프타임시 연산되는 거고요.. 이제 감이 좀 오실겁니다. 이런식으로 됩니다. 하나더 설명해야 할게 있는데 루프를 돌때마다 추가되는 자리의 연산에 쓰이는 앞의 연산결과의 자리가 한 자리씩 증가한다는겁니다. 2회차때는 S2+S7 같이요. 자세한건 코드를 참고하시면 됩니다.

이제 남은건 배열크기 정하는거와 루프횟수와 16byte를 채우는 방법입니다. 여기서 패스워드가 30자리이햐여야 하는 이유가 나옵니다. 루프횟수는 1792~2040 안에서 돌게됩니다. 총 11비트를 쓰게 되고  너무 많이 돌면 배열공간 낭비에 연산시간도 길어질거 같아 범위를 이렇게 정했습니다. 혹 불안해서 좀 더 돌려야 겠다는 분들은 앞에 남는 5bit를조정하시면 되겠지요..

그리고 뒤에 3비트를 111로 고정했습니다. 그러니까 0000011100000000 이 되는거죠.

에.. 그리고 이 루프횟수 산정과정에서 8로 나누어 떨어지는 값이 나와야 하는데 이걸 비트 끝 세자리를 0으로 채우게 했습니다. 그러니까 가운데 남는 비트수는 5개가 되는겁니다. 2의 5승은 32고 0을 빼면 31입니다.

이 5비트에 패스워드 자리수를 채워넣습니다. 1 ~ 30까지이겠지요. 31까지 해도 상관없습니다. 1차이..;;
여기서 나오는 11자리의 비트값이 배열의 크기와 루프의 횟수가 되겠습니다. 루프한계의 카운터가 증가해서 결국에 11자리의 값과 같아지는 시점에서 끝나게 되어있습니다. 말로 설명드리기 어려우므로 코드를 참고하세요.

이렇게 배열이 알 수 없는 값으로 채워지게 됩니다. 이제 16byte를 채우는 일이 남았는데요. 8개의 값을 선택해서 채워 넣습니다. 배열 전체의 값을 이용해 8개의 숫자를 구할수도 있겠습니다만. 그냥 하나씩 찍는게 편합니다. 여기에서 11bit 숫자를 구할때 뒤의 3bit를 0으로 채운 이유가 나옵니다. 8로 떨어지는 숫자가 나오니 배열크기 를 8로 나누어 나오는 값만큼 카운터 해서 8개 구하면 8개의 숫자를 집어낼 수 있습니다. 역시 자세한건 코드를 보시면 금방 이해하실 수 있습니다. 이러한 연유로 로또 프로젝트라고 불러볼까도 생각중입니다. 8개의 숫자찍기..;; 로또..흐음,,

이렇게 하여 대망의 128bit의 숫자가 나왔습니다. 이제 클라이언트는 ID와 계산되어진 128bit를 서버에 전송합니다. 그러면 서버는 DB에서 ID를 검색해서 얻은 패스워드와 클라이언트에 전송한 키를 가지고 앞의 연산을 다시 합니다. 그렇게 얻은 키와 클라이언트에서 전송되어진 키가 동일한지 검사해보면 됩니다. 그리고 한번 인증된 난수값은 DB에 저장해서 다시 그 난수값을 사용하지 않으면 됩니다. 그러면 같은 값이 전송되어 오는걸 볼 일은 거의 없어지겠지요.

또한, 코드를 열어보시면 알겠지만 코드를 수정해서 혼자쓰시는거면 상관없으십니다만, 배포는 안되십니다. 수정사항이 발생했을경우에는 제게 연락해 주시면 감사하겠습니다.

에에.. 마지막으로 이 글의 내용과 같은 내용의 글을 게시, 게재 하는것은 안되십니다. 링크를 넣어주세요. 어차피 tistory 서비스를 이용하는거라 트래픽 많이 걸려도 돈 제가 안 내는 겁니다.ㅋ