2016년 6월 24일 금요일

XOR을 이용한 암호화

XOR은 CPU에서 제공하는 연산으로, 이 연산의 [A ^ B = C 의 경우 두 값을 알면 나머지 한 값도 알 수 있다]는 성질을 이용하여 암호화를 할 수 있다.

XOR을 이용하여 암호화를 진행하면 다음과 같은 모양이 된다.


평문을 16진수로 바꾸어(아스키 코드) 키와 XOR 연산을 했고, 그 결과를 가지고 있다가 복호화 해야 하는 경우 다시 나만 알고 있는 키로 XOR 하여 원문을 구할 수 있다.

아주 빠른 속도로 암호화/복호화를 할 수 있지만 단점이 많다. 가장 큰 문제는 뚫기가 쉽다는 것. 키의 크기와 키 자체를 알아내기가 쉽다.

만약 어떤 프로그램에서 채팅을 암호화 한다고 하면(난이도를 쉽게 하기 위해) 채팅창에  "AAAAAAAAAAAAAAAAAAA"라고 써본다. 그리고 날라가는 패킷을 보면

6E2AE83 6E2AE83 6E2AE83 6E2AE83 .... 6E2AE83 6E2AE83 6E2AE83 6E2AE83

이렇게 돼 있는 것을 볼 수 있을 것이다. 만약 XOR을 사용해서 암호화 했다는 것을 알면 (가장 흔한 방법임으로 한 번 시도해볼 수 있음) 패킷을 보면 같은 문자인데 4바이트 단위로 암호화된 문자가 반복되고 있다는 것을 알 수 있다. 

그러면 이제 다음을 계산해본다.

6E2AE83 XOR 41414141 (AAAA의 아스키 코드 값)

그럼 계산기에 다음과 같은 값이 나오고, 그 값은 KEY가 된다.

47A3EFC2

이렇듯 쉽게 키를 알아낼 수 있고, 키를 알아내지 않더라도 전달되는 데이터의 일부를 변경할 수 있다는 문제점도 있다. 단순히 특정 비트-바이트의 값을 수정하는 것 만으로도 원하는 데이터를 변형할 수 있다.


2016년 6월 20일 월요일

Storing(데이터 저장)


Database in Files

  • 데이터베이스는 파일의 집합으로 저장된다. 각 파일은 레코드의 연속이고, 레코드는 필드의 연속이다.
  • 간단한 접근
    • 레코드의 크기가 정해져 있다
    • 각 파일은 한 가지 타입의 레코드로만 이루어져 있다
    • 서로 다른 파일은 서로 다른 릴레이션을 위해 사용된다. 이 경우가 가장 구현하기 쉽다. 가변 길이 레코드는 나중에 살펴본다
  • Fixed-Length Records (고정 길이 레코드, 크기 n)
    • i 번째 레코드는 byte n * (i - 1) 에 위치한다
    • 레코드의 접근은 간단하지만 레코드가 디스크 블록에 걸쳐서 나뉘어질 수 있다
      • 하지만 레코드가 경계에 걸쳐있지 않게 해야 한다
  • 레코드의 삭제
    • 레코드를 실제로 지우는 것이 아니라 삭제할 레코드를 free list 에 링크한다


Free List

  • 첫 번째로 삭제된 레코드의 주소를 파일의 헤더에 저장한다
  • 이 첫 번째 레코드에 두 번째로 삭제된 레코드의 주소가 저장된다. 계속 반복한다 (linked list)
  • 주소가 저장된다는 것은 해당 레코드의 주소를 가리키는 "포인터"를 저장한다는 것이다
  • 공간 효율을 높이기 위해서
    • 일반 값들을 저장하기 위해 있는 공간을 재사용 하여 다음 빈 레코드의 포인터를 저장한다
    • 사용 중인(값이 들어있는) 레코드에는 포인터를 저장하지 않는다
  • 새 레코드를 추가할 때 free list의 항목들을 사용한다

Variable-Length Records

  • 가변 길이 레코드는 데이터베이스 시스템에서 몇 가지 경우에 가끔 사용된다
    • 한 파일에 여러 타입의 레코드를 저장할 때
    • 레코드의 타입이 한 개 이상의 필드에서 가변 길이를 허용할 때
  • 가변 길이 레코드는 Slotted Page Structure를 가진다
    • 파일은 페이지의 집합이다
    • Slotted Page의 헤더는 다음의 정보를 포함한다
      • 레코드 엔트리의 개수
      • 블록의 빈 공간의 마지막의 위치
      • 각 레코드의 위치와 크기
      • 페이지 안에서 레코드의 위치가 옮겨질 수 있다. 이렇게 하면 각 레코드 사이에 빈 공간이 없이 유지할 수 있다. 이를 위해 헤더의 레코드에 대한 진입점이 업데이트 되어야 한다
    • 포인터는 레코드를 직접적으로 가리키면 안 된다
      • 대신 레코드는 헤더에 저장된 레코드에 대한 진입점을 가리켜야 한다


Organization of Records in Files

  • Heap
    • 레코드의 위치는 파일 안에 공간이 있다면 어디던 위치할 수 있다
  • Sequential
    • 각 레코드의 search-key를 기준으로 레코드를 순서대로 저장한다
  • Hashing
    • 각 레코드의 일부 속성에 해시 함수가 계산되어 있다
      • 결과는 파일 내 어떤 블록에 레코드가 위치해야 할지 알려준다
  • 각 릴레이션의 레코드는 서로 다른 파일에 저장될 수 있다. 
  • multi-table clustering file organization 에서는 서로 다른 릴레이션의 레코드가 같은 파일에 저장될 수 있다
    • 연관된 레코드를 같은 블록에 저장함으로써 I/O를 최소화하기 위함이다

Sequential File Organization

  • 모든 파일을 순서대로 접근해야 하는 경우에 적합하다
  • search-key를 기준으로 레코드 내 파일이 정렬된다
    • 정렬된 파일은 효율적으로 검색이 가능하지만 유지하기가 어렵다
  • 삭제
    • 포인터 체인을 이용하여 삭제된 튜플을 건너뛴다
  • 삽입
    • 레코드가 삽입되어야 할 위치를 찾는다
      • 만약 빈 공간이 있으면 그 곳에 삽입한다
      • 만약 없다면, overflow block에 삽입한다
      • 두 경우 모두 포인터 체인이 갱신 되어야 한다

Multi-table Clustering


  • 멀티 테이블 클러스터링을 사용하여 여러 개의 관계를 한 개의 파일에 저장한다
    • 여러 개의 릴레이션을 모두 조회해야 하는 쿼리에는 적합하다
    • 한 개의 릴레이션만 조회해야 하는 쿼리에는 좋지 않다
  • 다양한 크기의 레코드가 결과로 나온다
  • 포인터 체인을 추가하여 특정 릴레이션의 레코드를 연결할 수 있다


Data Dictionary Storage

  • Data Dictionary( 혹은 system catalog )는 메타데이터를 저장한다
    • 릴레이션들에 대한 정보
      • 릴레이션의 이름
      • 각 릴레이션의 속성의 타입의 이름
      • 뷰의 정의와 이름
      • 제약 조건
    • 사용자와 비밀번호 같은 접근 정보
    • 뷰와 그 뷰의 정의
    • 물리적인 파일 구조 정보
      • 어떻게 릴레이션이 저장되어 있는가(sequential/hash/...)
      • 릴레이션의 물리적 위치
      • 인덱스
    • 카탈로그식 구조
      • 디스크의 관계적 표현
    • 카탈로그 표현의 예
      • 릴레이션의 집합