For a better world

최근 많은 Redis 서버가 해킹당해 악성 봇넷으로 사용되고 있다고 한다. 그 이유는 Redis 서버에 인증없이 접속할 수 있다면 Redis 내부 명령어를 통해 악성코드를 실행할 수 있기 때문이다. 최근 Node JS로 개발 중인 서비스에서 캐시 DB로 Redis를 설치해 사용했다. 로컬에서 사용하니 실제로 서버 운영할 때 보안설정 하면되겠거니와 하며 인증없이 접속할 수 있도록 했었다. 하지만 로컬에 설치했던 Redis는 기본적으로 모든 네트워크와 연결 수립을 허용하는 것을 인지하지 못한 오판이었다. Redis는 기본 포트로 6379를 사용한다. 해커들은 6379 포트가 열린 IP를 브루트포싱하며 악성코드 실행을 위해 지속적으로 Redis 서버를 스캐닝 중에 있다. 다음과 같이 말이다.

redis-cli.exe를 통해 'monitor' 옵션을 설정해주면 내 Redis 서버를 스캐닝하는 외부 IP와 PORT를 확인할 수 있다. 또 만약 외부 IP에서 내 redis 서버에 임의의 key와 value를 설정하면 위 모니터링에 의해 값 설정 로그가 출력된다. 해커는 Redis 서버에 저장된 key-value를 탈취할 수 있지만, 휘발성격의 중요성이 떨어지는 데이터를 담는 Redis에선 key-value 탈취로 인한 피해보다 value에 악성페이로드를 담아 실행했을 때의 피해가 더 클 수 있다. 

위 info 로그는 "redis-cli -h <IP> -p 6379 info" 명령을 수행하면 발생하는 로그다. 실제로 실행해보면 아래와 같이 서버, 클라이언트, 메모리, CPU 등의 각종 정보를 조회할 수 있다. 세부적으로 운영체제 정보나 설정파일 경로를 획득할 수 있으니 해커 입장에서 이후에 페이로드 구성에 활용할 수 있다.

위 각종 정보를 살펴보던 도중 Clients 영역에서 connected_clients가 3인 것을 볼 수 있었다. 로컬에서 사용했는데 연결된 클라이언트가 존재할 수 있는지 궁금해졌다. client list라는 명령어가 있었고 이를 통해 살펴보니 모르는 외부 IP와 연결되어 있었다. (나머지 2개는 실행했었던 redis-cli monitor와 redis-cli client였다.)

IP 주소를 조회해보니 어디 상하이가 찍혀 나왔다. 사이트에 들어가보니 e-commerce 관련 회사 홈페이지였고 C&C 서버로 쓰이고 있는 것 같다. 

연결을 끊어줘야겠단 생각이 들었고 찾아보니 clinet kill 명령이 존재했다. 이를 통해 아래와 같이 중국 IP와의 연결을 끊어주었다.

이렇게 Redis 서버 보안에 주의를 돌리게 된 이유는 크게 두 가지다. 첫 번째는 지난밤 PC에서 비프음 보다 더 강렬한 소리가 났다. 이게 무슨 소리지?라고 어떻게 하면 이런 소리가 나지?라고 생각했다. 간단하게 윈도우 디펜더를 돌린 결과 아무 이상 없어 넘어갔다. 하지만 두 번째로 오늘 인증없이 접속 가능한 Redis 서버가 많고 많은 서버가 봇넷으로 사용되고 있음을 알게 됐다. 혹여 지난밤 소리와도 관련있지 않을까하여 Redis에 설정된 key 값과 운영체제에서 남기는 여러 로그를 분석해보았지만 다행히도 의심되는 흔적은 발견되지 않았다. 털리진 않았지만 이후 보안 설정도 개발과 병행해야겠단 생각으로 이어지게 됐다. 

따라서 보안 설정 방법을 알아보던 중 KISA가 발간한 클라우드 취약점 점검 가이드에 Redis 시스템 취약점 점검 가이드가 있었고, 가이드에서 말하는 4가지 보안 설정을 해주었다. 첫 번째는 Redis 인증 패스워드 설정이다. Redis config 파일을 살펴보면 SECURITY 영역에 'requirepass'가 있다. 기본값은 주석처리되어 있지만 주석을 해제하고 우측에 인증 패스워드 값을 설정해준다.

두 번째는 binding 설정이다. 기본적으로 Redis 서버는 모든 네트워크와 연결 될 수 있다. 만약에 bind가 주석처리 되어 있다면 말이다. bind의 기본 값이 주석처리 되어 있지만 이를 해제하고 로컬(특정 IP)에서만 접속할 수 있도록 한다. 

세 번째는 Slave 읽기 전용 모드 설정이다. redis는 master-slave 구조를 갖는다. master에 붙는 slave는 read-only 권한만을 가져서 master의 자원에 write할 수 없어야 한다. 하지만 이는 이미 아래와 같이 기본 설정으로 되어 있을 것이다. 그대로 두면 된다. 

네 번째는 rename-command 설정이다. Redis에서는 보안 설정을 목적으로 rename-command를 제공한다. 이는 명령어를 다른 이름으로 치환하는 역할을 한다. 가령 예를 들어 CONFIG 명령을 사용하기 위해서는 b840fc로 시작하는 해시와 같은 예측할 수 없는 값으로 설정할 수 있다. 또는 CONFIG ""을 통해 아예 CONFIG 명령을 사용할 수 없도록 만들 수 있다.

보안 설정 미흡으로 시스템이 털리는 것은 사소한 판단에서도 기인할 수 있음을 느끼게 됐다. 앞으론 서버 보안 설정에 주의를 더 기울일 수 있도록 해야겠다. 다음에 Redis 서버 설치한다면 위 4가지 설정을 제일 먼저 하는 걸로. (그나저나 최근 이따금씩 PC나 다른 장치에서 들리는 비프음 같은 것은 뭘까 싶다.)

(PS: requirepass 주석해제 및 값 설정으로 패스워드 설정이 안된다면 redis-cli에서 "config set requirepass <password>" 명령어로 설정할 수 있음)

Reference

[1] KISA 클라우드 취약점 점검 가이드

정보보안학 석사 과정을 졸업한지 1년 쯤 되어가고, 관심분야도 보안에서 딥러닝으로 바뀐지 꽤 오래 되었네요. 불현듯 자기 전 작년 종합시험 준비로 고통받던 때가 떠올라 이 글을 쓰게 됐습니다. 재학 기간 동안 두 번의 시험 기회가 있었고 첫 번째 기회를 날리는 고배를 마신 뒤 절치부심하는 마음으로 정리한 내용입니다. 중간/기말/종합시험 모두에 어느 정도 도움이 되리라 생각합니다. 가급적 논리적 서술이 가능하도록 정의, 배경, 특징, 장점, 단점, 차이점, 방법, 활용, 종류, 목표 등을 고려해 작성하였습니다. 아래에 예상 질문들은 강의 내용을 총 정리하다보니 자연스럽게 시험에서 이런 것을 물어볼 것 같다고 예상한 질문과 답안들입니다. 중간에 예상 답안이 부재한 경우는 2가지 이유입니다. 첫 번째는 교수님께서 매학기 수업마다 조금씩 설명을 더 해주거나 덜 해주는 파트가 있어 듣지 못해 정리할 수 없었던 부분입니다. 두 번째는 얼추 설명은 해주셨지만 정확히 이해 못하고 모호하게 알고 있는 부분은 지웠습니다. 댓글로 추가해주신다면 업데이트 하도록 하겠습니다. 또 틀린 부분이 있다면 지적해주시면 감사하겠습니다. 참고로 아래 내용들은 강의 요약 내용을 바탕으로 작성한 것이므로 포함하지 않는 내용과 설명들이 있습니다. 원본이 필요할 경우 댓글 남겨주시면 보내 드리겠습니다. 전체 글 내용은 고려대학교 정보보호대학원 김승주 교수님 보안공학 강의 내용을 기반으로 작성되었습니다.
 

보안공학이란 무엇인가?

H/W와 S/W를 만드는 개발 단계인 요구사항 분석, 설계, 구현, 배포, 유지보수에 이르기 까지 각 단계마다 모두 보안을 고려하고 제품을 판매하는 단계에서도 보안내재화가 이루어졌는지 제대로 이루어졌는지 확인하는 것이다.
 

보안공학의 목표는 무엇이고 왜 보안공학은 어려운가?

보안공학은 trusthworthy(dependable)한 시스템을 만드는 것을 목표로 한다. 보안공학은 random한 에러를 다루는 소프트웨어공학과 달리 random한 에러와 함께 의도적으로 발생한 intentional 에러도 함께 다루기 때문에 더 어렵다.
 

보안공학의 핵심인 Define & Design Approach, Shift left testing, traceability는 무엇인가?

• define & design approach: 보호해야할 자산을 정확하게 식별한 다음, 자산의 중요도와 이에 따른 요구사항을 정의하고 설계하는 것을 의미한다.
• shift-left testing: 매 개발 단계마다 testing을 수행 함을 의미한다. shift-left testing에서 보안 담당자의 역할은 개발자가 testing에 사용할 수 있는 도구를 만들어 공급하고, 개발자가 진행한 testing에 대해 적절성 여부를 검증하는 작업을 진행한다. 이러한 shift-left testing은 자동화가 가능하고, 이른 단계에서 testing을 진행할 수 있다는 장점이 있다.
• traceability: 

만약 보안공학에서 보안내재화 개발 프로세스를 통해 요구사항분석부터 설계, 구현까지 완벽히 수학적으로 다 증명돼도 모의해킹이 필요한가?

모든 것을 수학적으로 증명했다 하더라도 모의해킹이 필요하다. 수학적 증명은 전제조건을 가지고 있으며 이 전제조건이 제대로 지켜지고 있는지를 검증하기 위해서는 모의해킹이 반드시 필요하다. 이는 수학적 증명과 모의해킹이 상호보완 하는 관계라고 볼 수 있다.
 

바람직한 S/W 요구사항 도출 조건의 6가지와 그 특징은 무엇인가?

• Unambiguity: 다른 사람이 요구사항을 검토한 결과는 동일해야 하며 요구사항에 모호함이 없어야 한다.
• Prioritization: 요구사항의 구현과 관련하여 우선순위가 부여되어야 한다.
• Verifiability: 요구사항이 제품에 적절하게 구현되어야 하고, 검증하기 위한 Security Testing Requirement도 함께 도출되어야 한다.
• Completeness: 모든 필요한 요구사항이 전부 도출되어야 한다. (지정된 모든 요구사항은 전달해야 하는 기능을 완전히 설명해야 한다)
• Correctness: 해당 요구사항은 자체 모순을 가지거나 충돌되지 않고 그 기능을 정확하게 설명해야 한다.
• Feasibility: 해당 요구사항은 자원 및 제약조건에서 실행 가능해야 한다.

보안성 평가에서 TCSEC의 보안등급 중 A2는 왜 사용하지 않는가?

• TCSEC을 처음 만들 당시 A2 등급인 Code Proof(Code Assurance)까지 넣으려고 하였다. 하지만 TCSEC을 제작자는 Code Assurance의 입증이 어렵다고 판단하여 마지막에 A2를 제거하고 A1만 남겼다. Code Assurance는 Software testing과 Software verification으로 구성되는데, 특히 software testing에서 만약 소스코드가 대략 10,000줄이 이상 넘어가게 된다면 포인터 등으로 인한 복잡성 때문에 수학적 안정성 입증이 어려워지기 때문이다. 

TCSEC의 단점을 서술하시오

보안등급평가에 있어 Assurance와 Functionality가 서로 분리되어 있지 않아, High Assurance임에도 불구하고 낮은 보안등급으로 평가하는 결점이 있다.
 

보안성 평가 표준인 CC, CAVP, CMVP, C&A, RMF A&A, DITSCAP에 대해 설명하시오.

• CC: (개념) 보안성 평가와 관련해서 가장 권위있는 국제 표준이다. 보안성 평가 국제표준(ISO/IEC 15408)의 공통평가기준(CC)에 따라 정보보호시스템의 기능 및 취약성을 평가/인증하는 제도이다. (배경) 미국의 TCSEC으로부터 유럽연합의 ITSEC, 캐나다의 CPCPEC, FC 등이 만들어지게 되었고 이를 만든 각국가의 평가기관들은 국가적으로 독립된 평가 기준을 통합하는 프로젝트를 시작하였고 이를 CC 프로젝트라 하였다. CC 프로젝트는 TCSEC의 단점을 보완하고 기존의 평가 기준들간의 개념적/기술적 차이를 통합하여 국제 표준화를 만들자는 목표로 추진되어 만들어 졌다. (목적) CC인증은 평가과정에서 IT제품(H/W, F/W, S/W)에 적용되는 보안 기능과 보증수단에 대한 공통의 요구 사항들을 제시한다. 이를 통해 독립적으로 수행된 보안성 평가의 결과들을 비교할 수 있도록 한다. 평가 결과는 소비자가 IT 제품이 그들의 보안 요구를 충족시키는지 결정하는데 도움을 줄 수 있다.
• CAVP (Cryptographic Algorithm Validation Program): 암호 알고리즘을 중심으로 제대로 구현되었는지를 검증한다.
• CMVP (Cryptographic Module Validation Program): 특정한 암호 모듈이 특정한 암호 알고리즘을 올바르게 구현했느냐에 대한 구현 적합성을 시험/인증 한다. CMVP와 CC의 공통점은 제품이 요구사항분석단계부터 설계, 구현에 이르기까지 보안내재화 프로세스를 충실히 따랐는가를 본다. 이것이 발전해서 C&A 제도가 되었다.
• C&A (Certification & Accrediation): 
• RMF A&A: 2015년 DoD Cyber Strategy를 발표했고, 이 내용은 전산시스템 뿐만 아니라 F35 스텔스 전투기나 무인 드론과 같은 첨단 무기체계들도 보안내재화 개발 프로세스를 적용하라는 것을 요구한 것이다. RMF A&A는 이러한 요구사항을 충족시키고 실제로 준수하였는지 평가하기 위해 만들어진 표준이다.

(다소 설명이 빈약하다 생각들어 몇몇 부분은 추가되면 좋을 것 같습니다)
 

CAVP, CMVP, CC, DITSCAP, NIST C&A, RMF A&A의 정의 및 비교와 국내외 정책비교를 서술하라.

EAL 보안성평가에서 낮은등급에서 높은등급이 되기 위해 필요한 조건은?

Requirements, functional specification, HLD, LLD, implementation에 대해 formal method로 정형명세화 하여 수학적으로 만족함을 입증하여야 한다.

Information Security, Information Assurance or Cybersecurity의 차이를 서술하시오

핵심 차이는 trusthworthy라고 할 수 있다. information security는 컴퓨터와 컴퓨터에 들어있는 전자적 정보를 지키는 것을 의미하며, cybersecurity는 사이버공간과 연동된 모든것을 지키는 것을 의미하는데 여기에는 digital과 non-digital 정보도 함께 포함된다.
 

걸프전이 최초의 Information Assurance인 이유는 무엇인가?

이 질문에 대해 답을 정리하진 못했습니다. 다만 이 예상 질문과 관련한 부분적인 내용들을 기술하면 다음과 같습니다.

• 걸프전의 맥락에서 사용되어 정리하고 가야할 용어인 information security와 cybersecurity가 있다. 두 용어의 큰 차이점이자 추구하는 목표는 trustworthy이다.
  • Information Security: 컴퓨터와 컴퓨터 속에 들어 있는 전자적인 데이터를 보호하겠다라는 의미를 가진다.
  • Informaton Assurance or Cybersecurity: 사이버공간과 연동된 모든 것을 보호하겠다라는 의미를 가지며, 그 모든 것은 전자적인 형태(digital)의 데이터여도 되고 전자적인 형태(non-digital)가 아니여도 된다.
• 걸프전은 정보보증(Information Assurance)이라는 패러다임 shift를 발생시킨 선구자 역할을 했다는 점에서 의미가 있다.
• 걸프전에서는 패러다임 shift가 information security에서 information assurance로 바뀌었고, 이는 적의 정보는 교란시키고 내 정보를 유지시키는 것이 중요하다고 인식하게 되면서 이를 위한 목표인 trustworthy를 달성하기 위함이다. 
• 걸프전을 통해 Information Assurance가 중요해졌다. 이는 원할때 Access 가능해야 하고, 그 정보는 항상 relability와 security를 유지 가능해야 함을 의미한다.

Risk Management란 무엇이고, 구성요소와 이에 대한 정의는 무엇인가?

Risk Management는 기본적으로 Risk를 제거하는 것이 아니라 줄이는 것이다. 하지만 Risk를 줄인다하더라도 잔존 위협(Residual Risk)가 남아있게 된다. 이 때 이 잔존 위협을 어떻게 잘 관리할지 고려하는 것을 Risk Management라고 한다. 참고로 이를 위해선 자산별, 중요도 별 등급화가 되있어야 Risk를 측정할 수 있다. Risk Management 방법은 크게 4가지로, Risk Transfer, Risk Avoidance, Risk Reduction, Risk Retention이 존재한다.

• Risk Transfer: 위협을 보험사와 같은 제 3자에게 전가하는 것을 의미한다.
• Risk Avoidance: 위협을 회피하는 것을 의미하는 것으로 단적 예로 스마트TV에 카메라 떼는 것과 같다.
• Risk Reduction: 보안 대책을 만들어 위험을 감소시키는 것을 의미한다.
• Risk Retention: 위험의 확률이 낮으면 위험을 안고 가는 것을 의미한다.

결과적으로 이를 통해 Risk Avoidance를 제외하고 어떤 것이 ROI가 높은지 비교하여 그에 맞는 대응책을 세운 뒤, 높은 리스크부터 낮은 리스크로 대응해야 한다.
 

Risk Assessment의 특징과 그 한계를 설명하시오.

Risk Assessment는 quantitative risk analysis (정성적), qualitative risk analysis (정량적)로 크게 둘로 나뉜다. 리스크 분석은 정량적으로 분석하는 것이 객관성을 담보할 수 있다는 장점이 있지만 적용하고자 하는 사람의 탄탄한 수학적 이론이 뒷받침 되어야 하므로 실적용엔 무리가 있다. 따라서 무기체계분석이나 자동차보안성평가와 같은 필드에서는 정성적 분석 방법을 사용하는 것이 특징이다. (Risk = Probability * Damage Potential)
 

Goldwasser의 Semantic security와 Shannon의 Perfect Secrecy의 차이점을 서술하시오.

• Shannon's perfect secrecy : 무한한 컴퓨팅 자원을 가진 passive attacker로 부터 암호문에서 평문에 대한 어떠한 정보(단, 1bit라도)도 누출되서는 안된다.
• Goldwasser's semantic security : 유한한 컴퓨팅 자원을 가진 passive attacker로부터 암호문에서 평문에 대한 어떠한 정보(단, 1bit라도)도 노출되서는 안된다.

MDTD(Model Driven Test Design)가 test case create에 도움이 되는 이유는?

testing하려는 대상을 작은 task 단위로 모델링하여 해당 task에 집중적으로 testing할 수 있기 때문이다.
 

Model Checking 이론을 바탕으로 Code Assurance를 달성하는 방법 및 프로세스를 상세히 서술하시오.

프로그램을 model로 만들고 model checker에 requirement(ex: correctness property)를 넣었을 때 model checker에서 model이 requirement를 충족하는지에 대한 여부를 Yes/No로 알려준다. 만약 No의 경우에는 counter measure도 함께 알려준다. 결과적으로 model checker를 통해 해당 프로그램의 model이 requirement를 충족하는지 판단한다. (Model Checker는 완전 자동화가 가능하다는 장점이 있고, Automatic Theorem Prover에 비해 적용 범위가 작다는 단점이 있다.)

데이터 거버넌스에 대해 설명하시오

데이터거버넌스의 핵심은 데이터 사일로(칸막이) 문제로 인해 도입된 개념으로 데이터 활용을 위한 전사적인 경영체계라 할 수 있다. 조직은 이러한 데이터 거버넌스를 통해 데이터 활용 계획과 데이터 보호 계획을 수립하여 활용도를 극대화 시켜서 궁극적으로 데이터 사일로를 제거하는 것을 목표로 한다.
 

14가지 Security Design Principle과 각각이 의미하는 바를 서술하시오.

• Least Privilege: 사람 또는 시스템에게 부여할 최소한의 권한을 부여하는 것을 의미한다. 하지만 이 최소권한의법칙을 지키기 위해 보안레벨을 사용자와 오브젝트 사이에 어떻게 설정해야 하는가는 쉽지 않다.
• Fail-Safe Default: 두 가지 의미를 가진다. 첫 째는 명시적 허용이 아니면 거부를 의미한다. 예를 들어 방화벽 룰셋에 명시되지 않은 패킷이 있을 경우 drop하는 것과 같다. 둘 째는 만약 프로그램이 비정상 상태로 빠질 경우, 바로 직전에 안전했던 상태로 돌아가는 것을 의미한다. 이를 통해 프로그램을 항상 안전한 상태로 유지시킬 수 있게 한다. 예를 들어 윈도우 블루스크린이 표시되어 먹통이 되는 상태로 빠지지 않게 하는 것과 같다.
• Economy of Mechanism: H/W, S/W를 개발할 때 가능한한 시스템을 단순하고 작은 사이즈로 설계하고 구현해야 함을 의미한다. 단순하고 작은 사이즈로 설계하는 것은 모듈화 설계와 같다. 장점은 요구사항을 달성하고 있는지 검증이 쉬워진다. 심플할수록 assurance level이 높아진다. simple and small이 의미하는 바는 검증하기 쉽도록하여 assurance level을 극대화 시킨다는 것이 핵심이다.
• Complete Mediation: 자원에 접근할 때 마다 반드시 그 권한에 대해 확인해야하는 것을 의미한다. 모든 접근을 전부 확인하는 것을 zero-trust라고 한다. 하지만 실질적으로 모든 접근에 대한 확인은 부하로 인한 속도저하가 심해서 구현하기 어려운 것이 특징이다.
• Design by Contract: 어떤 일을 처리할 때 항상 확인된 인터페이스를 통해서만 해당 일을 처리해야함을 의미한다. 예를 들어 중요한 시스템일수록 사전 정의된 인터페이스 또는 사전 정의된 프로토콜을 통해서만 중요 자원에 접근할수 있도록 하는 것을 의미한다.
• Open Design: 어떤 시스템을 만들었을 때 그 시스템의 설계도나 소스코드가 공개되어도 안전도가 유지될 수 있어야 한다는 것을 의미하고, 시스템의 안전성을 설계도나 소스코드의 폐쇄성에 의존하지 않아야 한다는 것을 의미한다. 예를 들어 군에서 같은 모듈을 사용하는 무전기를 분실하게 되면 리버싱하여 소스코드를 알아낼 수 있기 때문에 시스템을 만들때 설계도나 소스코드가 공개됐다고 전제한 다음 시스템을 만들라는 것이다. 그래서 만약 안전하다면 오픈 디자인 원칙에 충실하다 할 수 있다. 동의어는 Kerckhoff's 법칙이라고도 하며, 반대말로 Security through Obsecurity 또는 Security by Obsecurity라고도 한다. 
• Seperation of Prvilege: 중요시스템에 접근할 때는 그 권한을 분산 또는 분리해야 함을 의미한다. 예를 들어 핵무기를 동작시킬 때 두 사람의 암호를 동시에 입력해야 작동하는 것과 같다.
• Least Common Mechanism: 시스템의 공통 모듈을 최소화해서 활용해야 함을 의미한다. 이는 보안에서 한 부분에 문제가 생겼을 때 다른 부분으로 파급되는 것을 최소화하는 것이 중요하기 때문이다. 하지만 현실적용에는 어려운 부분이 있는데 이는 공통모듈을 쓰면 생산성은 높아지나, Economy of mechanism의 개념과 정면으로 위배되는 특징이 있기 때문에 시스템을 만들다보면 이 개념에 충실하기 쉽지 않은 것이 특징이다.
• Psychological Acceptability: Usable Security라고도 부르며 이는 시스템이 사용하기 편리해야 함을 의미한다.
• Defense in Depth: 보안 시스템을 둘 때 계층을 두어 한 계층이 뚫히더라도 다음 계층이 막아줄 수 있도록 시스템을 설계해야 함을 의미한다.
• Effective Logging: 로그를 잘 남겨야 함을 의미하는 것으로, 개인정보보호법으로 인해 로그에 어떤 정보가 들어가면 안되는지 또한 중요해진 것이 특징이다.
• Build In, Not Bolt On: 시스템을 개발한 다음 보안제품을 사서 쓸 것이 아니라, 처음 만들 때 보안이 Build In되도록 만들어야 함을 의미한다.
• Design for Updating: 업데이트를 어떻게 할 것인가를 설계해야 함을 의미한다.
• Centralized vs Decentralized: 중앙화 시킬 것인지 분산화 시킬 것인지를 의미한다.

What is 'sound'?

Threat Modeling의 개념과 절차적 특징을 서술하시오.

Threat Modeling은 목표 시스템에 대한 어떤 위협요소가 없는지를 공격자의 입장에서 체계적으로 분석할 수 있는 방법론을 의미한다. 이를 통해 목표 시스템의 attack surface 식별, 얼마만큼의 위협이 발생하는 가를 측정할 수 있다. 또한 보안대책과 보안대책에 대한 테스트와 같은 일련의 청사진을 도출해낼 수 있다는 것이 특징이다. 전반적인 프로세스는 다음과 같다.

1. DFD를 통해 우선적으로 모델링한 후 지켜야할 자산을 중요도 별로 우선순위를 식별한다.
2. 분석대상 시스템에 대해 취약점정보와 관련된 attack library를 수집한다.
3. 공격자의 관점에서 STRIDE를 이용하여 어떤 element에 취약점이 매핑될 수 있는지를 확인한다.
4. 매핑된 정보를 기반으로 공격시나리오를 생성 후 attack tree로 표현한다.

SRIDE: 모델링된 시스템에서 element 별로 공격자의 입장에서 취약점을 도출할 수 있는 보안위협모델링 방법이다. Spoofing(위장), Tampering(변조), Repudiation(부인), Information DIsclosure(정보유출), Denial of Service(서비스거부), Elevation of prvilege(권한상승)으로 구성되어 있다. SRIDE에는 분석 방법이 2가지로 stride-per-element와 stride-per-interaction이 있다. stride-per-element는 element 별로 S,T,R,I,D,E 공격이 발생할 수 있을지 검증하는 것을 의미하고 stride-per-interaction은 trust boundary를 넘나드는 데이터 흐름들에 대해 중점적으로 분석하는 방법을 의미한다.
 
Attack Tree: 수집한 취약점 정보를 엮어 공격시나리오화 시킬 수 있는 방법으로, 하나의 목표 별로 하나의 Attack Tree가 만들어지는 것이 특징이다.
 
DREAD: DREAD는 5가지 항목으로 구성되어 있고 각각은 다음과 같다.

• Damage Potential: 공격자가 굉장히 민감한 데이터를 탈취하거나 파괴할 수 있음을 의미한다.
• Reproducibility: Timing winodow가 크거나 작음을 의미하는 것으로, Timing window가 작은 예시로는 컴퓨터가 부팅될 때만 공격이 가능하고 Timing winodw가 큰 예시로는 컴퓨가 켜져 있으면 언제든 가능할 때를 의미한다.
• Exploitability: 공격 프로그램으로 만들기가 얼마나 쉬운가를 의미한다.
• Affected Users: 공격으로부터 영향을 받는 사용자가 얼마나 많은가를 의미한다.
• Discoverability: 해당 취약점을 얼마나 발견하기 쉬운가를 의미한다.

Risk score = DREAD/5이다. 이러한 Risk score의 단점은 절대적이지 않고 사람마다 상대적인 것이다. 따라서 2010년 이후 MS에선 더이상 사용하지 않고, security response center bulletin ratings를 사용해 사람마다 오차가 생기는 것을 막고자 하였다.
 

LINDDUN을 설명하시오.

LINDDUN은 DFD를 작성한 뒤 개인정보보호의 관점으로 보안위협식별을 수행하는 방법이다. LINDDUN을 이루는 구성요소와 이에 대한 설명은 아래와 같다.

• Linkability: 
• Identifiability: 
• Non-repudiation: 
• Detectability: 
• Disclosure of Information: 
• Unawareness: 
• Non-compliance: 

TARA를 설명하시오.

Threat Assessment and Remediation Analysis로 2011년 MITRE에서 만들어진 것으로, 국가의 지원을 받는 해커들이 있다는 전제하에 위협모델링을 어떻게 할 수 있을까를 위해 만들어졌다. 일반적인 해커와 달리 국가의 지원을 받는 해커는 기존의 Threat Modeling을 할 수 없는데 이는 투입비용의 한계가 없기 때문이다.
 

Structured Threat Assessment Process란 무엇인가?

핵심은 모의해킹과 위협모델링(Threat modeling)을 합쳐서 수행하는 것을 의미한다. 

 
Formal Method의 특징을 서술하시오

어떤 시스템에 대한 요구사항을 수학적 기법을 이용하여 요구사항을 정확하게 기술하고 그 요구사항이 제대로 달성되었는지를 검증하는 것을 의미하는 것으로, 크게 formal specification과 formal verification으로 구성된다.
 

Security Policy와 Security Policy Modeling의 개념과 차이점을 서술하시오.

• security policy는 security requirement의 집합으로, 어떤 것을 보호해야하고 그것을 어떻게 보호할 수 있을까를 의미한다.
• security policy modeling은 좁은 의미로는 security policy를 정형명세로 기술해둔 것을 의미하고, 넓은 의미로는 security policy를 정형명세로 기술하고 그 요구사항이 제대로 충족되었는지를 검증까지 하는 것이다. 검증에는 두 가지 의미가 포함된다. requirement 간의 모순점이 없는지를 검증하고, 설계도가 요구사항을 전부 반영하여 제대로 설계되었는지를 검증한다.
• 또한 보안성평가의 국제표준인 CC을 확인하면 EAL1~EAL7이 있는데 EAL4까지는 security policy를 제출할 것을 요구하나 EAL5부터는 security policy model을 제출할 것을 요구한다. 여기서 model은 정형명세로 제출하는 것을 의미한다.

DAC의 개념, 특징, 장단점 등에 대해 서술하시오.

DAC은 임의적 접근통제정책을 의미하는 것으로 데이터의 소유주가 데이터에 접근가능한 권한을 결정할 수 있고, 운영체제에 의해 시행되는 것이 특징이다. 장점으로는 필요한 사람에게 권한을 부여할 수 있는 최소권한법칙을 달성하기 쉽고 협업이 편하다는 장점이 있다. 반면 카피에 취약한 구조로 내가 권한을 부여했던 사람이 다시 다른 사람에게 데이터에 접근하는 권한을 부여할 수 있다는 것이 단점이다. 따라서 군에서는 이를 사용할 수 없는데 이에 대안으로 만들어진 것이 강제적 접근정책인 MAC이다.
 

MAC의 개념, 특징, 장단점 등에 대해 서술하시오.

MAC은 강제적 접근통제정책을 의미하는 것으로 주체와 객체의 보안등급에 따라 허가 또는 제한하는 것이 특징이다. 중앙집중형으로 엄격한 보안을 제공할 수 있는 것이 장점이나 모든 접근에 대해 확인해야 하므로 성능 저하가 발생할 수 있다는 단점이 있다. 또한 최소권한의법칙을 충족하지 못한다는 단점이 있고, 이 때문에 보안레벨로만 접근권한을 통제하지 않고 Compartment의 개념을 추가하여 최소권한의법칙을 달성하고자 하는 MLS 정책이 만들어졌다.
 

BLP 모델의 개념, 특징, 장단점 등에 대해 서술하시오.

벨과 라파듈라는 MLS 정책또한 충분하지 않기 때문에 Define and Design Approach를 해야 한다고 주장하며 1973년 BLP 모델을 제시하였다. 가장 먼저 달성해야할 것을 정의하고, 접근통제정책이 올바르게 시행되려면 SS-Property, *-Property가 만족해야되어야 한다고 하였다.

• SS-Property (Simple Security Property): 기존의 MLS의 특징인 사용자가 가진 보안등급과 compartment의 범위가 접근하려고 하는 object의 보안등급과 compartment 범위보다 커야지만 object에 접근할 수 있음을 의미한다.
• *-Property (Start Property): 기존 MLS를 충족하는 시스템은 SS-Property만 충족한다는 단점을 보완하기 위해 나온 개념으로 subject가 SS-property를 만족했다는 전제하에 보안등급이 높은 object에서 데이터를 읽고 낮은 등급의 object에 쓰면 안된다는 것을 의미한다. 어떤 것을 충족하고 어떤 것을 충족하지 않는지를 명확히 표현하는 것이 중요하다는 것을 보였다는 점에서 의의가 있는 것도 특징이다.

BLP 모델은 security property를 기밀성 관점에서만 고려하기 때문에 무결성 관점을 고려하지 못한다는 단점이 있고, Covert Channel에 취약하다는 단점이 있다.
 

BLP 모델에서 권한이 높은 프로세스와 권한이 낮은 프로세스간의 통신 방법은 무엇인가?

권한이 높은 프로세스가 권한이 낮은 프로세스와 통신을 해야할 때가 있지만 권한이 높은 곳에서 낮은 곳으로의 데이터가 쓰이는 것을 막았기 때문에 데이터를 전달할 수 없다는 단점이 있다. 이를 해결하기 위한 대안이 2가지가 있는데 첫 번째는 subject security level을 순간적으로 낮추는 방법이 있고, 두 번째는 *-Property를 위반해도 되는 Trusted subject group을 생성하여 서로간의 등급이 다르더라도 데이터를 주고 받을 수 있도록 하는 방법이 있다. 첫 번째 방법을 실제로 구현한 것이 MULTICS이다.
 

McLean이 BLP 모델에서 비판한 평정속성은 무엇을 의미하는가?

Tranquility(평정속성): 시스템이 한 번 세팅되면 사용자들의 권한은 바뀌지 않음을 의미한다. 벨과 라파듈라는 BLP 모델의 전제를 평정속성으로 하였지만 McLean으로부터 전제조건이 위반되었다고 지적하였다.
 

BLP 모델에서 주어진 formal method를 참고하여 SS-Property를 표현하시오.

SS Property = No Read Up

• A state $(b, M, f)$ satisfies the SS-Property if
  • $\forall (s, o, a) \in b,$ such that $a \in \{read, write\}$
  • $f_O(o) \leq f_S(s)$
  a subject can only observe objects of lower classification.

read 또는 write를 하고 있는 모든 subject와 object에 대해 object의 보안등급이 subject의 보안등급보다 낮으면 모든 action은 read 또는 write이다.
 
 

BLP 모델에서 주어진 formal method를 참고하여 *-Property를 표현하시오.

BiBa 모델의 개념, 특징, 장단점 등에 대해 서술하시오.

BLP 모델이 나온 뒤 기밀성만 다룬다는 단점을 보완하기 위해 무결성 관점을 다루기 위해 나오게 된 것으로 BLP 모델과 logical dual이라 할 수 있다. 무결성 관점에서는 정보의 흐름이 높은 곳에서 낮은 곳으로 가야한다. BLP 모델과 동일하게 SS-property와 *-Property를 동일하게 주장하였다.

• SS- property (Read up)
  • subject의 integrity level이 object의 integrity level보다 높거나 같아야 데이터를 읽을 수 있음을 의미한다.
• *-property (Write down)
  • subject의 integrity level이 object의 integrity level보다 높거나 같아야데이터를 쓸 수 있음을 의미한다.

클락 윌슨의 상용 컴퓨터 시스템과 군 전용 시스템에 대한 비교 논문의 의의를 서술하시오.

1983년 클락윌슨이 상용컴퓨터시스템의 보안정책과 군에서 쓰는 보안정책의 비교논문을 낸 바 있다. 내용의 핵심은 군에서는 Integrity가 중요하지 않을지 모르나 상용시스템에서는 Confidentiality보다 Integrity가 훨씬 중요하기 때문에 Integrity와 관련한 security requirement를 명확히 정의하고 디자인하는 것이 중요하다고 주장하였다. 이 논문은 사람들이 접근통제정책이 confidentiality 뿐만 아니라 Integrity도 중요하다고 생각하게 되었다는 점에서 의의가 있다.
 

Clark-Wilson Model을 설명하시오

가장 큰 특징 & 종류 및 개념
Clark-Wilson 모델의 가장 큰 특징은 Well formed transaction을 정의했다는 것이고 이는 절차가 잘 정의된 프로세스를 의미한다.
Clark-Wilson Model은 CDIs, UDIs, TP, IVPs의 4가지 요소로 구성된다.

• CDIs: Contrained Data Items의 약자로 Integrity가 중요한 데이터셋을 의미한다.
• UDIs: Unconstrained Data Items의 약자로 Integrity가 중요하지 않은 데이터셋을 의미한다.
• TP: Transformation Procedures로 일종의 업무 매뉴얼을 의미하는 것으로 업무 매뉴얼에 따라 절차가 엄격히 정의된 프로세스를 통해서만 접근 가능한 것이 특징이다. 예컨데 CDIs에 접근하려는 USER는 반드시 TP를 통해서만 접근해야 한다.
• IVPs: Integrity Verification Procedures의 약자로, 주기적으로 CDIs의 무결성이 올바르게 지켜지고 있는지를 검증한다.

이러한 Clark-Wilson 모델의 예는 은행시스템이 있다. 은행에서 돈과 관련된 모든 데이터는 CDIs에 해당하고 이외의 데이터는 UDIs에 해당한다. TP는 입금, 출금, 계좌이체와 같이 명확히 정해진 절차가 있고 이 절차에 따라 움직이는 것을 의미한다. 그리고 어제 은행이 가지고 있던 돈에서 오늘 들어온 돈을 더하고 나간 돈을 빼는 것과 같이 정기적으로 검증과정을 거치는 것을 IVPs라고 한다.
Clark-Wilson 모델은 크게 두 개의 업적을 가진다. 첫 번째는 상용시스템에서 Integrity가 중요할 수 있음을 강조했다는 점이다. 두 번째는 기존 BLP, Biba모델은 사용자가 데이터에 접근한다 생각하였지만 Clark-Wilson은 사용자는 프로그램(TP)에 접근하고 프로그램이 데이터에 접근한다고 하였다.
 

HRU (Harrison-Ruzo-Ullman) 모델에 대해 서술하시오.

HRU 모델은 BLP 모델의 전제조건이었던 평정속성을 위반했다는 McLean에 비판에 의해 권한이 바뀌어도 보안을 유지할 수 있는 방안을 연구한 모델이다. 동작원리는 권한을 요구하는 요청이 올 경우 임시로 matrix를 변경해보고 state가 잘 유지되는지를 검증한다. 예를 들어 matrix를 바꿨을 때도 기존과 동일하게 SS-property가 충족되는지를 체크하는 것이다. 충족된다면 바꾸고 충족되지 않으면 바꾸지 않는다는 것이 기본 개념이다. 하지만 HRU 모델은 state가 잘 유지되는지를 체크하는 것이 쉽지 않다는 단점이 있다. 따라서 HRU 모델에서는 제약조건을 추가하였다.

• Monotonic protection system: destory나 delete 명령이 없는 시스템을 의미한다.
• Monocondtional system: 각 명령의 조건 부분에 하나의 조건만 있는 시스템을 의미한다.
• Finite number of subjects: subject의 개수가 finite한가?

Chinese Wall 모델에 대해 서술하시오.

Chinese Wall 모델은 HRU 모델이 더 발전된 형태이다. 접근권한이 사전에 세팅되고 요청이 있을 때마다 접근권한이 동적으로 변경되는 특징을 가진다. 또한 Chinese-Wall 모델은 subject의 접근권한이 바로 직전에 한 행동에 의해 다음 접근권한이 결정된다는 특징을 가지고 있다. 예를 들어 변호사가 CITI 은행의 변호를 맡는 순간 KB, NH, SH와 같은 다른 은행에 대한 접근권한이 차단된다. 하지만 S-OIL, GS 칼텍스와 같은 이해상충집단(COI, Conflict Of Interest)이 아닌 클래스의 데이터에는 접근할 수 있다. Brewer와 Nash가 Chinese-wall 모델을 정의할 때도 SS-property와 *-Property를 충족해야 한다고 하였다.

• SS-Property: 데이터에 접근하는 동시에 이해상충집단에 해당하는 데이터의 접근하지 못함을 의미한다. 하지만 만약 이해상충되더라도 접근을 계속 유지하고 있거나 완전히 COI Class에 속한다면 접근 가능하다.
• *-Property: Information flow에 있어 이해상충집단간의 un-sanitised information이 흐르지 못하도록 하는 것이다. 또한 write access는 이해상충집단에 속해있는 object가 현재 읽혀지지 않고 있거나, 또는 un-sanitised information을 가지고 있을때만 허용된다.

RBAC에 대해 서술하시오

RBAC은 역할기반접근통제정책이다. 기존의 DAC, MAC에서의 접근권한이 사람에게 부여되지만 실제 세상에서의 접근권한은 사람에게 부여되는 것이 아닌 그 사람의 역할에 부여된다는 점에 기반하였다. (그림 그리기) User와 Role사이에 Session이 있고, 이는 동시에 여러 개의 역할을 할당받기 위해 필요한 개념으로, 윈도우에서 창을 여러개 띄워 놓는 것과 같다. RBAC에서 role이 분리되어야할 경우가 2가지가 존재하는데 첫 번째로는 static seperation of Duty로 예를 들어 한 사람이 총무의 역할을 맡으면서 동시에 감사의 역할을 맡을 수 없음을 의미한다. 두 번째로는 dynamic seperation of Duty로 예를 들어 은행 업무를 하고 있는 직원의 역할을 가진 동시에 고객의 역할을 할 수없음을 의미한다.
 

우리나라의 리스크 관리에 있어 최대 문제점은 무엇인가?

데이터의 중요도에 따른 데이터의 등급화가 되어 있지 않다는 것이 핵심이다. 중국의 경우에도 의료, 금융, 개인정보 등을 Low, Medium, High, Very High와 같이 4단계로 나누나 우리나라의 경우 그렇지 않다. 또한 데이터의 중요도에 따라 데이터의 등급을 나눈 뒤 망분리와 망연계가 명확히 되어야 하지만 잘 이루어지지 않고 있는 것이 실태이다.
 

Covert Channel은 무엇이고 Side Channel과 어떻게 다르며 이 Covert Channel을 해결하기 위한 방안은 무엇인가?

Covert Channel은 설계자가 의도하지 않았던 방향으로 데이터를 유출하는 채널을 의미한다. Side Channel과의 차이점은 Covert Channel의 경우 송신자와 수신자간의 Covert Channel에 대한 약속이 필요하고, Side Channel의 경우 송신자가 필요하지 않고 수신자 입장에서 별도의 채널을 통해 정보를 추출하는 것이다.
Covert Channel은 기본적으로 전부 막을 수는 없으나 이를 해결하기 위한 방안으로 Lattice Based 모델이 있다. Lattice Based 모델은 수학에서 이야기하는 Lattice 구조를 이용하여 정보가 흘러도되는 것과 흐르면 안되는 것을 포멀하게 정의하는 모델이다. Lattice 구조가 성립하는 조건으로는 GLB와 LUB가 있고, 모든 Subset에 대해서 GLB와 LUB가 존재할 경우에 해당한다. 하지만 현업에서 실제로 사용하기에는 복잡하다는 단점이 존재하고 이를 조금 더 적용하기 쉽고, 구현에 용이하게 만든 모델이 Non-Interference 모델이다. Non-Interference 모델은 covert-channel과 Inference attack을 주로 다룬다.
 

Execution Monitor의 개념과 특징을 서술하시오.

• Execution Monitor는 이벤트가 발생할 때 시스템 정책들에 위반되는 사항이 있는지 확인하는 시스템이다. 구체적으로 어떤 함수가 error 상황을 야기하도록 하는 위험한 함수인지 아닌지를 검증하는 것으로, 그 함수 외부로 undesirable exception이 propagate 되지 않는지 또 그 결과에 대한 report가 제대로 되는지를 모니터링 한다.
• Execution Monitor는 운영체제 안에서 동작하는 것으로 프로그램을 한 줄 한 줄 실행시켜보며 이벤트가 발생했을 때 EM 시스템이 괜찮은지 검증 후 괜찮다면 실행시키고 문제가 발생하면 빠져나오는 시스템이다. EM을 활용하면 DAC, MAC 정책에서 정책을 위반 여부를 관찰할 수 있는 것이 특징이다. 하지만 Information flow security 같이 정보가 제대로 흐르는지 아닌지는 EM으로 체크할 수 없다. 예를 들어 DDOS 같은 경우는 EM으로 체크할 수 없는데, 이는 EM이 항상 과거의 데이터를 보기 때문에 DDOS와 같이 미래를 보아야 하는 공격은 체크할 수 없는 단점이 있다. 즉 EM으로 모든 보안정책을 제어하기에 한계가 있고 불충분하기에 RM에 다른 요구사항이 추가되어야해서 복잡한 구조를 가지게 된다.

Liveness property와 Safety property에 대해 서술하시오.

Liveness property는 프로그램은 언젠가 종료될 것이지만 언제인지 알 수 없다는 의미를 가지며, Safety property는 나쁜일은 생기지 않는다는 것을 의미한다. Liveness property는 미래를 보아야 하기 때문에 어렵고 safety property는 과거를 보기 때문에 비교적 쉽다. Execution Monitor는 safety property에 속하는 것은 전부 측정할 수 있다. 하지만 EM으로는 모든 보안정책을 제어하기엔 한계가 있고, 불충분하기에 Reference Monitor에 다른 것이 추가되어야 해서 복잡한 구조를 가지게 된다.
 

Reference Monitor의 세 가지 기본원칙을 설명하시오

• Reference Monitor: 감시 프로그램인 Reference Monitor는 운영체제에서 발생하는 모든 이벤트를 감시할 수 있어야 하고 정책에 위반되는 것을 차단해야 한다.
• Simplicity & Assurance: RM이 중요하기 떄문에 수학적으로 증명해야 한다. 하지만 RM이 복잡하다면 수학적 증명이 어려워진다. 따라서 RM을 단순하게 만들고 이를 통해 Assurance를 높여야 한다.
• Evaluation & Certification: 평가제도를 운영하여 정부가 이를 받아들이도록 해야 한다.

Reference Monitor의 세 가지 요구조건을 더 명확히 표현하여 설명하시오

• Complete Mediation: RVM이 있어서 운영체제에서 발생하는 모든 이벤트를 통제할 수 있어야 한다. (Reference Validation Mechanism)
• Tamper-Proof: RVM은 해커가 리버싱할 수 없어야 하고 non-bypassible하여 해커가 우회할 수 없어야 한다.
• Verifiable: RVM은 충분히 작아서 수학적으로 검증 가능해야 한다.

Trusted Computing Base (TCB)를 설명하시오.

Security Kernel과 다른 보호메커니즘을 결합한 것으로, TCB는 신뢰가 필요한 모든 H/W와 S/W가 포함된다. (Security kernel: Reference Monitor를 실제로 구현해둔 것을 의미한다.)
 

Authentication vs Identification을 설명하시오.

Authentication은 사용자 인증을 의미하고, Identifiaction은 개인 식별을 의미한다. 예를 들어 네이버에 아이디와 비밀번호로 로그인하는 것은 사용자 인증에 해당하고 범죄현장에서 지문을 발견하여 데이터베이스에서 매칭하여 범인을 알아내는 것은 개인 식별에 해당한다. 내가 나임을 증명한다면 Authentication이고, 타인이 나를 식별한다면 Identification이다.
 

High Assurance Crypto Library란 무엇인가?

설계부터 구현까지 수학적으로 전부 증명된 것을 의미한다.
 

Secure Design Principle 12가지를 서술하시오

1. Least Privilege: 사람 또는 시스템이 필요로 하는 최소한의 권한만 부여하는 것을 의미한다.
2. Fail-Safe Defult: 명시적 허용이 아니면 거부를 의미한다. 예를 들어 방화벽 룰셋에 설정되어 있지 않다면 패킷을 drop하는 것과 같다.
3. Economy of mechanism: H/W나 S/W를 만들 때 설계를 심플하고 작게 만들어야 함을 의미한다.
4. Complete Mediation: 중요 자원에 접근하려는 것을 모두 통제할 수 있어야 함을 의미한다.
5. Design by Contract: 정해진 인터페이스나 프로토콜로만 중요 자원에 접근할 수 있어야 함을 의미한다.
6. Open Design: 설계도의 소스코드가 공개되더라도 안전도를 유지할 수 있어야 할 수 있어야 함을 의미한다.
7. Seperation of Privilege: 중요 권한은 분리되어야 함을 의미한다.
8. Least Common Mechanism: 공통 모듈 사용 최소화를 의미하는 것으로, Economy of mechanism과 정면으로 위배되는 특징이 있다.
9. Psychological Acceptability: 심리적으로 사용하기 좋아야함을 의미하는 것으로 Usable security라고도 불린다.
10. Defense In Dept: 보안 시스템을 둘 때 계층적으로 구성해야함을 의미한다.
11. Effective Logging: 효율적인 로깅이 가능해야 함을 의미한다. 최근 개인정보보호법으로 인해 무엇을 기록하지 말아야 할지도 고려해야 하는 것이 특징이다.
12. Built In, Not Bolt on: 시스템을 만들고 나서 보안을 고려하는 것이 아니라 시스템을 만들때 함께 보안을 고려하는 것을 의미한다.

Design Assurance를 쉽게 달성하는 방법은?

Design Assurance를 쉽게 달성하기 위해서는 전제조건을 맞추어 두면 된다. 또한 가정(Assumption)이 많으면 쉽게 달성할 수 있다.
 

Design Assurance를 입증하는 방법에 대해 서술하시오

크게 2가지로 나뉘며 Symbolic method와 Confidential method로 나뉜다.

• Symbolic Method:  수학적 증명을 자동화하는데 사용하는 방법으로, 주로 리플레이 공격을 분석하는데 사용된다. 하지만 confidential method와 달리 복잡한 공격에 대해서는 증명이 어렵다는 단점을 가진다.
• Computational Method: 정교한 공격에 대해 수학적 증명이 가능한 방법으로 골드아서와 미칼리가 주로 기여한 분야이다. Symbolic method와 달리 자동화시키기 어렵기 때문에 대부분 manual하게 증명하는 것이 특징이다.

SPN (Substitution-Permutation Network)의 특징을 서술하시오.

주로 대칭키인 AES 암호화에 사용되는 네트워크로, 네트워크 내부적으로 크게 Diffusion과 Confusion이 있다. Diffusion은 확산으로 암호문과 평문사이의 관계를 알아낼 수 없도록 복잡하게 섞어주는 것을 의미한다. 주로 permutation을 통해 데이터의 순서를 바꾸는 방법(P-Box)을 사용한다. Confusion은 혼돈으로 키와 암호문간의 관계를 알아낼 수 없도록 복잡하게 섞는 것을 의미한다. 주로 Substituion을 통해 다른 symbol로 바꾸는 방법(S-box)을 사용한다.  이러한 Diffusion과 Confusion을 극대화하기 위해서는 permutation과 substitution을 반복적으로 하면된다. 이러한 대칭키 암호에서 Design Assurance를 입증하기 위한 전제조건으로는 S-box와 P-box는 안전한 것으로, 특히 S-Box는 랜덤하다는 전제가 필요하다.
 

RSA 암호의 특징에 대해 설명하시오

디피와 헬만이 공개키 암호를 정의하였고 이러한 정의를 충족하여 만들어진 최초의 공개키 암호가 RSA 암호이다. RSA 암호의 안전성은 소인수분해에 기반한다. 하지만 RSA 암호의 해독방법은 소인수분해 말고도 존재하여 안전성은 증명되지 않았다. 대신 소인수분해 문제를 제외하고 RSA 암호에 대한 공격기법이 개발되면 그에 맞추어 업그레이드 시키는 것이 특징이다.
 

레빈암호 시스템에 대해 설명하시오

레빈암호시스템은 RSA 암호시스템과 달리 수학적구조가 아름답다. RSA 암호시스템은 기본적으로 안전성은 소인수분해 문제의 어려움에 기반하지만 소인수분해이외에도 암호를 해독할 수 있는 방법이 존재한다. 따라서 RSA 암호를 해독할 수 있는 공격 방법이 만들어질 때 마다 암호시스템을 업그레이드한다. 이와는 달리 레빈암호시스템은 해독가능한 방법이 소인수분해 밖에 없다는 것을 수학적으로 증명되어 있다. 이러한 레빈암호시스템은 Design Assurance를 만족하는 최초의 공개키 암호라는 것에 의의가 있다.
 

Random Oracle Model이란 무엇인가?

전제조건이 해쉬암호는 안전하다는 것으로, 정확히는 해시암호의 출력은 랜덤함을 전제하는 것을 의미한다. 이를 통해 기존의 theoretical한 암호시스템과 practical한 암호시스템이 결합되기 시작되었다는 점에서 의의가 있는 것이 특징이다.
 

Perfect Secrecy의 특징을 서술하시오.

Perfect secrecy는 샤논이 만든 개념으로 passive 공격자가 무한한 컴퓨팅 파워가 있더라도 암호문으로부터 어떠한 정보도 얻어낼 수 없는 것을 의미한다. 하지만 이는 대칭키에서는 성립하지만 공개키암호에는 적용할 수 없다는 단점을 가진다. 이는 공개키가 있기 때문에 전수조사로 비밀키를 찾을 수 있기 때문이다.
 

Semantic Security의 특징을 서술하시오

기존의 샤논이 만든 개념인 perfect secrecy의 단점인 공개키에서는 적용할 수 없다는 단점을 보완하기 위해 골드아서 박사가 정의한 개념으로 "유한한 컴퓨팅 파워를 가진 공격자가 암호시스템으로부터 그 어떠한 1비트의 정보도 알아낼 수 없음"을 의미한다. design assurance의 관점에서 요구사항이 한 단계 진화할 수 있었고 이후에는 이러한 정의를 충족하는 암호 알고리즘이 만들어지게 되었다는점에서 의의가 있다.
 

공개키암호의 message space가 작으면 발생할 수 있는 문제는 무엇이고 해결방법은 무엇인가?

공개키 암호에서 message space가 작다면 대칭키 암호와 달리 전수조사를 통해 해독이 가능하다는 문제점이 있다. 이를 해결하기 위한 방안으로는 같은 메시지더라도 출력값이 달라지게 하기 위해 랜덤패딩을 붙이는 방법이 있다. 이러한 랜덤패딩을 붙이는 방법이 Polynomial Security(IND-CPA)이다. 즉, 암호알고리즘이 polynomial security를 만족하려면 랜덤패딩이 필요하다.
 

Polynomial security (IND-CPA)의 특징을 서술하시오.

기존의 공개키암호시스템에서 message space가 작다면 대칭키암호시스템과 달리 전수조사를 통해 알아낼 수 있다는 단점을 보완하기 위해 나온 개념으로, 동일한 평문이 동일한 암호문을 출력하지 않도록 랜덤패딩을 붙이는 방법을 의미한다. 즉, polynomial security를 만족하려면 랜덤패딩이 필요하다. polynomial security는 semantic security와 다르게 표현되었지만 동치라는 특징을 가진다. 즉 암호알고리즘에 랜덤패딩을 추가하면 암호문으로부터 그 어떠한 정보도 노출되지 않는다.
 

암호문을 위/변조하는 Active Attacker를 막는 설계 방법은 무엇인가?

크게 3가지 방법이 있다. 첫 번째는 전자서명을 사용하는 것이다. 암호문에 전자서명을 붙여서 보내는 방식으로 가능하다. 하지만 공개키 암호문을 설계하는데 전자서명도 사용해야하기 때문에 비효율적인 방법에 해당한다. 두 번째는 Message Authentication Code를 붙이는 방법이 있다. 하지만 이 또한 MAC 알고리즘의 안전성에 대해 증명해야한다는 단점이 있다. 세 번째는 고정된 형태의 패딩을 추가하는 것이다. 하지만 semantic security를 만족하려면 랜덤한 패딩을 추가해야한다. 이러한 문제점을 해결하기 위한 방법이 OAEP이다.
 

OAEP(IND-CCA)의 특징을 서술하시오.

IND-CCA의 경우 기존의 골드아서와 미칼리의 semantic security가 passive한 공격자로 전제한다는 단점을 보완하기 위해 나온 개념으로 active한 공격자에서도 암호시스템을 안전하게 만들기 위한 방법이다. 이는 고정된 형태의 패딩을 추가하는 방식으로 충족시킬 수 있다. 하지만 semantic security를 만족하기 위해서는 랜덤패딩을 추가하여야 한다. OAEP는 이러한 고정패딩과 랜덤패딩을 함께 추가하는 방법으로 Chosen Cipher Attack에 안전하다는 특징을 가진다.
 

Non-malleability (NM-CCA)의 특징을 서술하시오.

전통적으로 암호문을 해독하거나 부분정보를 끄집어내는 방법과 달리 암호문을 해독하지 않고 암호문에 변조를 가하는 것을 의미한다. 이를 통해 암호문이 갖추어야 할 requirement가 semantic security와 non-malleability가 되었다. 하지만 후에 이는 다르게 표현되었으나 동치임이 확인되었고 결국 semantic security, polynomial security, non-malleability는 다르게 표현되었지만 하나라는 요구조건임을 확인하였다는 점에서 의의가 있다.
 

암호에서 Active 공격을 방어하기 위해 사용하는 방법은 무엇인가?

암호에서 active 공격이 많이 발생하기 때문에 암호알고리즘만 사용하지 않고 MAC과 함께 사용되는 경우가 많다. 크게 3가지 방법이 있다.

• Encrypt-and-MAC: 메시지에 대해 암호화시키고 그것과 별개로 메시지에 대해 MAC 코드를 만드는 방법이다.
• MAC-then-Encrypt: 메시지에 대해 MAC을 만들고 원래 메시지 뒤에 붙인 뒤 전체를 암호화시키는 방법이다.
• Encrypt-then-MAC: 메시지를 먼저 암호화시키고 그 암호문에 대해 MAC을 붙이는 방법이다.

여기서 주요 쟁점은 설계방법에 따른 안전도 문제(합성보안 문제)가 제기되는데 통상적으로 Encrypt-then-MAC이 가장 안전하다고 알려져있다.
 

Compositional Security란 무엇인가?

합성보안문제로 예를 들어 블록체인에서 떠오르는 분야인 DeFi에서도 사용되는 개념이다. DeFi는 머니레고시스템이라고도 부르는데 이는 소스코드가 공개되어 있어 자신들이 만들고자하는 서비스를 만들어 DeFi 시스템에 붙이는게 가능하다. 이 때 공개된 소스코드에 취약점이 있다면 DeFi 전체시스템에 대해 합성보안 문제가 야기된다. 또한 BlackHat 2017에서 발표되었던 WPA2의 사례와 같다. 유닛테스트에서는 안전함이 증명되었지만 통합테스트(합성)에서는 안전하지 않았다.
 

Zero-knowledge 시스템의 특징을 서술하시오.

암호화 알고리즘과 전자서명은 단방향으로 보내면 되는 1-way 형식이지만 세상에는 interactive하게 동작하는 것이 많다는 점에 착안하여 어떤 client, server, verifier가 interactive하게 동작했을 때 안전하다는 것은 어떻게 입증하는가와 같은 문제가 대두되면서 도입된 개념이다. 영지식 증명의 개념은 3가지 조건을 만족해야 한다.

• 완전성(Completeness): 어떠한 정보가 참일 경우에 정직한 증명자는 정직한 검증자에게 그것을 납득시킬 수 있어야 한다.
• 건전성(Soundness): 어떤 정보가 거짓일 경우에 부정직한 증명자는 거짓말을 통해 정직한 검증자에게 그것이 ‘참’임을 납득시킬 수 없어야 한다.
• 영지식성(Zero-Knowledge): 검증자는 어떤 정보가 참 혹은 거짓이라는 사실 이외에는 아무것도 알 수 없어야 한다.

CC와 EAL7에서 소프트웨어 검증보다 소프트웨어 테스팅에 의존하는가? or Code Assurance의 한계는 무엇인가?

Software Fault, Error, Failure를 설명하고 왜 구분해야 하는지에 대한 이유를 서술하시오.

• Software Fault: 소프트웨어 자체가 가지고 있는 결함을 의미하는 것으로 문제가 발생하는 근본 원인이다.
• Software Error: 불안정한 프로그램 상태를 의미하는 것으로 어떤 값을 넣어 software의 문제가 있는 Falut까지 도달하면 내부적으로 이상상태가 발생하는 것을 의미한다.
• Software Failure: Fault까지 도달하여 내부적으로 불안정한 프로그램 상태가 외부로 표출되는 것을 의미한다.

구분 없이 모두 합쳐서 bug라 부르면 안된다. 명확히 구분해야 test case가 제대로 되었는지 아닌지 구분할 수 있기 때문이다. 만약 모두 합쳐 bug라 부른다면 test case를 설명할 방법이 없어진다.
 

Software Fault의 종류는 무엇이 있는가?

• Random Fault: 사람의 실수에 의해 발생하는 Fault를 의미한다.
• Intentional Fault: 의도성을 가지고 발생시킨 Fault를 의미한다.

Software Testing과 Debugging의 차이점을 서술하시오.

Software testing은 소프트웨어를 체크할 수 있는 test value인 input값을 뽑아내는 것을 의미한다. 반면 debugging은 외부로 표출된 failure를 보고 결함이 있는, 문제의 원인이 되는 fault부분을 찾아가는 것을 의미한다.
 

Static testing과 Dynamic testing의 차이점을 서술하시오

Static testing은 프로그램을 실행시키지 않고 테스팅하는 것을 의미하는 것으로 소스코드, 바이너리, 중간언어가 될 수 있다. 반면 Dynamic testing은 프로그램을 실행시키면서 테스팅하는 것을 의미하는 것으로 체계적인 테스팅을 위해 DART라는 프로그램을 사용하기도 한다.
 

Black box testing이 먼저인가 White box testing이 먼저인가 그리고 이유를 설명하시오.

black box testing이 먼저이다. 개발공정상 개발단계 전까지 코드가 없기 때문에 white box testing을 할 수 없다. black box testing은 바이너리가 아닌 코드가 없이 테스팅하는 것을 의미한다. 때문에 설계문서와 같은 모든 것들이 black box testing의 대상이 된다. 이후 코드가 완성되면 white box testing까지 하여 정교한 테스팅이 가능해진다.
 

Validation과 Verification의 차이점을 서술하시오

Validation은 사용자의 마음에 맞도록 만들어졌는가를 의미하는 것으로 Verification보다 어려운 것이 특징이다. 여기에는 사용자의 요구를 전부 분석하여 requirement를 제대로 도출하였는지까지가 들어간다. Verification은 specification이 있고 이를 통해 requirement가 제대로 도출되었다고 전제하고 requirement가 specification대로 만들었는지 검증하는 것으로 validation보다 쉽다는 것이 특징이다.
 

test case 선정 시 잘 도출하였는지 평가하기 위해 네 요소를 사용하는데 이 네 요소와 특징에 대해 서술하시오.

4가지 요소는 RIPR이다.

• Reachability: test input 값이 문제의 근원인 소프트웨어 fault가 있는 지점까지 도달해야 함을 의미한다.
• Infection: test input 값이 문제의 근원인 소프트웨어 fault까지 있는 지점까지 도달하여 프로그램 내부 상태가 불완전한 상태(error state)로 만드는 것을 의미한다.
• Propagation: 불완전한 상태가(erorr state)가 전이되어 최종적으로 Incorrect한 final state로 가는 것을 의미한다.
• Revealability: 프로그램의 Incorrect한 final state가 실제로 외부로 드러나는 것을 의미한다.

Test requirement와 Coverage Criteria의 관계는 무엇인가?

test case → test set → test requirement → coverage criterion → coverage criteria의 단계를 가지는 구조이다.
둘 간의 관계를 예시를 들면 다음과 같다. 예를 들어 젤리의 맛이 6가지와 색이 4가지가 있을 때 Coverage Criteria는 두개가 될 수 있다. 젤리봉투를 뜯었을 때 맛이 6가지가 있어야 한다는 C1의 Criterion과 색이 4가지가 있어야 한다는 C2의 Criterion이다. C1과 C2를 합쳐 Coverage Criteria라고 하며, 이를 통해 test requirement를 도출할 수 있다.
 

소프트웨어를 모델링하는 대표적인 방법을 서술하시오. (Coverage Criteria를 줄 때 사용하는 방법)

소프트웨어를 모델링하기 위해 사용하는 방법은 크게 4가지로 Input domain, Graph, Logical Expression, Syntax Structure 방식이 있다. 어떤 방법론을 사용하느냐에 따라 coverage criteria는 다른 형태로 주어진다.

• Input Domain model based testing: 함수에 들어가는 입력 값만보고 테스트케이스를 만드는 계획을 세우는 방법을 의미한다.
• Graph model based testing: 소스코드를 그래프의 형태로 바꾸어 모델링하는 방법으로 소프트웨어 테스팅에 가장 많이 사용되는 기법이다.
• Logical Expression model base testing: 조건문만 가지고 test case를 도출하는 모델링 방법으로, predicates라고도 부른다.
• Syntax Structure model based testing: 문법 규칙을 주고 문법 규칙에 따라 test case를 생성하는 모델링 방법이다. 그래프만큼 모델링에 많이 사용되며 grammar-based modeling이라고도 한다.

Generator와 Recognizer를 설명하시오.

Generator는 coverage criteria를 주면 알아서 test case를 만들어주는 것을 의미하며, Recognizer는 test case가 주어지면 어느 coverage까지 달성하는지를 분석해주는 것이다.
 

Graph model based testing의 특징을 서술하시오.

소스코드를 그래프의 형태로 바꾸어 모델링하는 방법으로 소프트웨어 테스팅에서 가장 많이 사용되는 기법이다. 크게 2가지 기법으로 Structural coverage criteria와 Data flow coverage criteria로 분류 된다. (분류 특징 서술하기). 그래프 모델링 기법은 소스코드에 사용하는 것이 주로 일반적이나 설계단계의 문서와 더불어 제품을 개발하는 여러 단계에 테스팅하는데 활용할 수 있다. 그래프 모델링에서 test case 도출을 어렵게하는 요소로는 루프가 있다. 기존에는 루프를 만나면 사이클을 한 번만 돈다고 가정하였으나 이는 abstraction gap이 크다는 단점이 존재한다. 따라서 이를 해결하기 위한 방안으로 touring, sidetrips, detours라는 prime path 를 사용하여 abstraction gap을 줄이려는 노력을 하고 있다.
 

Call-Graph를 설명 하시오

Control Flow Graph, Data Flow Graph 이외에 Call Graph가 있는데 이는 어떤 모듈이 어떤 모듈을 부르는가에 대한 호출 관계를 표시하는 그래프이다. 모듈을 어떻게 분배시킬까에 대한 sub-system level에서 사용되며, 결과적으로 design integration test에 활용한다.
(좀더 포멀하게 바꿀 수 있으면 좋겠습니다.)
 

Logical Expression Model based testing에 대해 서술하시오.

조건문만 가지고 test case를 도출해내는 모델링 방법으로 이를 predicates라고도 한다. logic expression은 소스코드에서 발견되는 predicates와 clause에 따라 이를 테스트할 수 있는 test case를 도출하는 것이 특징이다. clause에는 major clause와 minor clause가 있다. major clause는 predicates를 결정짓는 핵심이되는 것을 의미하며, minor clause는 그 이외의 것을 의미한다. 효율적인 test case 도출을 위해서는 major clause를 도출해내는 것이 중요하다. 하지만 logical expression 모델링 방법은 프로그램을 실행시키전까지는 파악하기 어렵다는 단점을 가진다. 예를 들어 어떤 값에 n을 나누거나 y를 나눌 때 어떤 값이 나올지 알기 어려운 것과 같다.
 

Syntax Structure Based Testing에 대해 서술하시오.

문법 규칙에 따라 test case를 생성하는 모델링 방법이다. Graph-based 모델링 방법만큼 많이 사용되며 Grammar-based modeling이라고도 한다. grmmar가 구성되면 두 가지 목적으로 사용가능하다. 첫 번째는 grammar에 맞춰 여러 test case를 생성할 수 있고, 두 번째로는 어떤 값이 grammar를 충족하는지에 대한 여부를 확인할 수 있다.
 

Structural Coverage Criteria과 Data Flow Coverage Criteria의 특징을 서술하시오.

Control Flow는 structural coverage criteria와 연계되고 Data Flow는 data flow coverage criteria로 연계된다. structural coverage criteria는 노드와 엣지로 그래프를 정의하고 분기(e.g. if)를 통해 프로그램이 실행되는 코드가 달라지는 것을 기준으로 하는 방법이다. 대표적으로 node coverage, edge coverage, edge-pair coverage, complete path coverage, specified path coverage 등이 있다.
data flow coverage criteria는 프로그램이 어떻게 변수가 정의되고 사용되는지를 기반하여 커버리지 기준을 적용하는 방법을 의미한다. 즉, 데이터 흐름 그래프상에서 각 변수의 def-use-pair가 다양한 방식으로 실행되도록 하는 기준이다. 대표적으로 all-defs coverage, all-uses coverage, all-du-paths coverage이 있다.
 

mutant에 대해 설명하시오

mutant는 원본 프로그램이 있고 일부를 바꾸었을 때를 의미한다. mutant는 크게 valid mutant와 Invalid mutant로 나뉜다. valid mutant는 시드값을 바꾸었을 때 그래머를 만족하는 mutant를 의미하며, Invalid mutant는 시드값을 바꾸었을 때 그래머를 만족하지 않는 mutant를 의미한다. 주로 mutation testing에 사용 된다.
 

mutation testing을 설명하시오.

grammar(subject)로부터 ground string(seed) 값을 뽑아낸다. 이후 ground string(seed)에서 일부를 바꾸면 mutant가 생성된다. 이 때 test case를 generate하여 ground string와 mutant에 각각 넣고 같은지를 비교하며 이를 mutation testing이라 한다. 쉽게 말해 원본 프로그램은 run tests on subject에 들어가고 변형된 프로그램은 run tests on mutant에 들어간다. 이후 test case를 생성하여 각각의 프로그램에 넣었을 때 원본 프로그램과 변형된 프로그램을 구분할 수 있으면 이를 mutant를 죽였다 표현하고 이를 mutation testing이라 한다. 
 

program-based mutation testing에 대해 서술하시오.

test case가 제대로 만들어졌는지 test할 때 주로 사용되는 testing 기법이다. coverage 개념과는 다르며, 얼마나 많은 mutant를 제거하였는지가 핵심이다. 즉, grammar를 따르지 않은 mutant와 grammar를 제대로 따른 원본을 test case가 구별해낼 수 있는 가이다.
 

여러 소프트웨어 테스팅 기법 중 grammar-based mutation testing이 가지는 특징은 무엇인가?

Input domain, graph, logical expression 등의 테스팅 기법과 달리 grammar-based mutation testing은 test case를 test 할 수 있다는 것이 가장 큰 특징이다. 또한 기본적인 grmmar를 정해두고 조금씩 변형해가며 input을 넣어보는 퍼징에도 효과적으로 사용할 수 있다.
 

Software verification의 특징을 서술하시오

software testing의 한계인 실제로 버그가 없음을 입증하기 위해 모든 가능한 인풋값에 대해 전부 테스트해보아야 한다는 것을 보완하기 위해 나온 것으로, software가 requirement를 충족하는지 충족하지 않는지를 수학적으로 증명하는 방법이다. 하지만 문제점은 어떤 software가 requirement를 충족하는지 하지 않는지를 증명하는 것은 undecidable problem에 속하기 때문에 이론적으로 software verification이 불가능하다고 입증되었다. 하지만 현실에서 마주하는 것은 모든 software가 아닌 특정 타입의 software이기 때문에 범위를 줄이게 되면 불가능하지 않다. software verification에서 사용되는 요소 기술의 종류는 symbolic execution, automatic theorem prover, model checker 등이 있다.
 

Concrete Execution이란 무엇인가?

프로그램을 실행시키면서 변수 값이 어떻게 변형되어 가는지 확인하며 프로그램이 제대로 동작하는지 하지 않는지를 검증하는 것이다.
 

Symbolic Execution에 대해 서술하시오.

기호실행은 프로그램에 구체적인 값을 넣지 않고 모든 것을 기호로 바꾸어 전개시키고, 실제 테스팅하고자 하는 영역의 방정식을 충족하는 값을 구하는 방식이다. 전개된 상태에서 방정식만 풀면 어떤 경로를 테스트할지 test case를 자동으로 뽑아낼 수 있다. 즉 testing input generation이 가능하여 어떤 경로로 갈지 바로 뽑아낼 수 있다는 것이 장점이다. 반대로 path explosion 때문에 적용이 쉽지 않은 것이 단점인데 이는 구체적인 값이 아니라 기호를 넣으면 길이가 긴 경로가 나올 수 있기 때문이다. 이에 대한 대안으로는 pre-conditioned symbolic execution으로, 이는 프로그래밍할 때 BOF와 같이 에러가 많이 발생할 수 있는 조건에 사용할 수 있다. 보안관점에서는 buggy path만 체크하면 경우의 수가 줄어 Exploitable한 path에 대해 symbolic execution하여 효과적인 test case 도출이 가능하다.
 

Automatic Theorem Prover에 대해 서술하시오.

software verification에서 자주 사용되는 요소 기술 중 하나이다. 프로그램을 정형명세로 바꾸어 표현하는 것이 특징이다. 구성요소는 3가지로 variable, precondition, postcondition이 있다. 만약 a와 b를 더한 결과인 result를 출력해주는 프로그램이 있다 가정할 경우 a,b,result는 variable에 해당하고 이에 할당된 초기값은 precondition에 해당한다. 마지막으로 a, b, result에 대한 관계는 postcondition에 해당한다. 프로그램이 전부 수행되었을 때 Automatic Theorem Prover가 자동으로 정형명세를 충족하였는지 검증하며, 이를 Floyd-Hoare Triple이라고도 한다.
 

Floyd-Hoare Triple에 대해 서술하시오.

Variable, Precondition, Postcondition으로 구성되는 것으로, Precondition {P}가 주어졌을 때 논리적 흐름에 따라 전개되면 반드시 Postcondition {Q}에 도달한다. 따라서 프로그램에 Precondition과 Postcondition을 정형명세로 바꾸어 중간 중간 끊어서 주게되면 실제 프로그램이 제대로된 논리 흐름을 따르는지 검증할 수 있는 것이 특징이다. 이러한 Precondition과 Postcondition을 정형명세로 표현하면 Theorem Prover가 정형명세를 지키고 있는지를 검증한다.
 

(Automatic) Theorem Prover와 Model Checker의 차이를 서술하시오.

Model Checker는 기본적으로 automatic theorem prover에서 확장된 개념이다. 둘간의 차이점은 크게 자동화 여부, 적용 범위, requirement 개수로 3가지다.
자동화여부: theorem prover의 경우 프로그램 중간중간에 precondition과 postcondition을 정형명세로 다 입력해주어야 하는 반자동이다. 반면 model checker는 프로그램을 모델로 바꾸고 모델이 도달해야할 요구사항을 준 뒤 충족했는지의 여부를 yes or no로 출력 가능한 것으로 완전 자동에 해당한다.
적용범위: theorem prover의 경우 반자동이기에 적용 범위가 넓어 많은 프로그램에 적용할 수 있다 반면 model checker는 적용할 수 있는 프로그램이 theorem prover 보다는 적다는 단점을 가진다.
requirement 개수: theorem prover는 반자동인 대신 체크할 수 있는 (security) requirement개수가 많고, model checker는 완전자동이지만 적용할 수 있는 (security) requirement 개수가 적다.
 

Model Chcker에 대해 서술하시오.

모델 체커는 프로그램을 모델링하여 모델체커에 넣고 도달해야할 requirement를 주어 도달여부를 검증하는 것으로, 관점을 조금 바꾸면 exploit을 자동 생성하는 도구를 만들어 counter example을 뽑을 수 있는게 특징이다. 아래와 같이 아키텍처가 구성된다(그림 그리기). 이를 활용하여 cyber grand challenge에서 취약점 탐지 자동화 도구가 나왔었다. 하지만 이는 모든 가능한 exploit 코드를 만들어지는 것은 아닌데 이는 취약 가능성이 높은 buggy path만 보기 때문이다.
 

1. 개인정보비식별화 개요

비식별화란 특정 개인을 식별할 수 없도록 하는 조치이다. 국회에서 데이터 3법이 통과되면서 도입되었다. 데이터 3법의 중요 내용 중 하나는 개인의 명시적 동의 없이 연구 목적으로 사용하기 위해서는 비식별화 조치가 이루어져야 한다는 것이다. 때문에 핀테크 기업이나, 금융 회사, 대학/연구소 등에서 연구나 서비스를 하기 위해 개인정보에 대한 비식별화에 대한 중요성이 증대되었다.

2. 비식별화에 사용되는 주요 개념

크게 개인정보, 가명정보, 익명정보로 3가지으로 구성된다. 아래 표가 핵심을 담고 있다.

개인정보

살아있는 개인에 관한 정보로 이름이나 주민번호 또는 영상이나 다른 정보와 결합해 개인 식별이 가능한 정보를 의미한다.

가명정보

개인정보의 일부를 삭제하거나 일부 또는 전부를 대체하는 등의 방법으로 추가정보 없이 특정 개인을 알아볼 수 없도록 처리한 정보이다.

익명정보

특정 개인의 주체를 알아볼 수 없도록 처리한 정보를 의미한다.

3. 비식별화 대상 자산 종류

자산 종류는 크게 식별자와 속성자로 구분되며 아래 표와 같다.

맨 아래에는 속성자가 있는데 속성자에 포함되는 내용은 아래 그림과 같다.

4.비식별화 조치 방법

5개의 처리기법과 17개의 세부기술로 구성되어 있으며 아래 그림과 같다.

Reference

[1] https://www.comworld.co.kr/news/articleView.html?idxno=49812

디피헬만 키 교환 프로토콜의 경우 간단한 형태이다. 예시를 들자면 A, B가 있을 때 A는 B에게 3을 보내고 B는 6에게 보냈다고 할 경우 서로 3과 6을 곱한 값인 18을 세션키로 사용하는 것과 같다.

세션키를 만들기 위해 각자의 개인키를 g의 승수로 취해 모듈러 연산을 한 다음 보낸다. Bob는 세션키를 생성하기 위해 Alice로부터 받은 $R_1$에 자신의 개인키인 $y$를 곱해주고,  Alice는 세션키를 생성하기 위해 해 Bob으로부터 받은 $R_2$에 자신의 개인키인 $x$를 곱하여 같은 세션키를 사용한다.

블록체인에서도 주로 언급되는 영지식 증명의 경우 아래 3가지 조건을 충족시켜야 한다.

Completeness(완전성): 어떤 문장이 참이면 정직한 증명자는 정직한 검증자에게 이 사실을 납득시킬 수 있어야 한다.

Soundness(건전성): 어떤 문장이 거짓이면 부정직한 증명자는 정직한 검증자에게 이 문장이 사실이라고 납득시킬 수 없어야 한다.

zero-knowledgeness(영지식성): 어떤 문장이 참이면, 검증자는 문장의 참거짓 이외에는 아무것도 알 수 없어야 한다.

암호학적으로 해시를 안전하게 설계하기 위해서는 크게 3가지 조건이 필요하다.

이를 해시의 3가지 성질이라 한다.

제 1역상 저항성(pre-image resistance)

• 주어진 output 값으로 원래의 input을 알아내기 어려워야 한다.
• 주어진 해시값 y로부터 $h(x)=y$를 만족하는 x를 찾는 것이 어려워야 함을 의미한다.

제 2역상 저항성(second pre-image resistance)

• 동일한 output을 가지는 input이외의 input'을 찾기 어려워야 한다.
• 해시함수 h와 x값이 주어졌을 때 동일한 y값을 내는 x`을 찾기 어려워야 한다.

충돌 저항성(collision resistance)

• 서로 다른 입력 값을 해시했을 때 같은 output이 나오기 어려워야 한다.
• 해시함수 h가 주어졌을 때 동일한 y값을 내는 $(x, x')$ 쌍을 찾기 어려워야 한다.

한마디로 말해 차례대로 $x, x', (x,x')$을 찾기 어려워야 한다.

1. Elgamal 암호 알고리즘 개요

Elgamal 암호는 공개키암호시스템으로서 디피헬만의 키교환과 같은 원리를 사용하는 것이 특징이다. Elgamal 암호는 이산대수 문제의 어려움에 기반하고 있다. 예를 들어 (x,g,p)가 주어졌을 때 y=g^x mod p는 계산하기 쉽지만, (y,g,p)가 주어졌을 때 x를 찾기 쉽지 않다는 것이다. Elgamal 암호는 Textbook-RSA보다 암호문의 길이가 2배나 길다. 하지만 동일한 평문에 대해 동일 암호문을 출력하는 Textbook-RSA와 달리 동일 평문에 대해 매번 다른 암호문을 출력하는 probabilistic한 성질을 가진다.

키생성

1. 큰 소수 $p$를 선택한다.

2. $1\leq d\leq p-2$의 범위에서 임의의 d를 선택한다.

3. $Z_p^*$에서 임의의 원시근 $e_1$을 선택한다.

4. $e_2=e_1^d\ mod\ p$를 계산한다.

암호화

1. 메시지 $m$과 랜덤 $r$을 선택

2. $c_1=e_1^r\ mod\ p$를 계산

3. $c_2=e_2^rm\ mod\ p$를 계산

4. $(c1, c2)$를 수신자에게 전송

복호화

개인키 d를 이용해 $c_2(c_1^d)^{-1}\ mod\ p$를 계산 → M 도출 가능

$c_2(c_1^d)^{-1}\ mod\ p$

= $c_2e_1^{-rd}\ mod\ p$

= $e_2^rm*e_1^{-rd}\ mod\ p$

= $e_1^{rd}me_1^{-rd}\ mod\ p$

= $m\ mod\ p$

2. Elgamal 암호 알고리즘과 KPA 공격

random number를 사용하지 않으면 Elgamal 암호는 KPA 공격에 취약하다. KPA 공격은 알려진평문공격으로 공격자가 평문에 대응하는 암호문 쌍 일부를 알고 있을 때다. 공격자는 이를 통해 새로운 평문에 대해 평문과 키를 알아내는 것을 목표로 한다.

방법 1

공격자는 자신이 알고 있는 평문 m과 $(c_1,c_2)$를 이용해 아래와 같이 계산가능하다.

$c_2=e_2^rm\ mod\ p$

$e_2^r=c_2m^{-1}\ mod\ p$

이때 공격자는 자신이 원하는 $m^*$에 대해 아래와 같은 과정을 통해 알 수 있다.

$c_1^*= e_1^r\ mod\ p$

$c_2^*=e_2^rm^*\ mod\ p$

일 때 이미 계산해둔 정보를 통해 아래와 같이 계산하여 $m^*$를 얻을 수 있다.

$(e_2^r)^{-1}c_2^ = m^*\ mod\ p$

방법 2

$[m]$
1) $C_1=e_1^r\ mod\ p$

2) $C_2 = e_2^r*m\ mod\ p$

$[m']$
1) $C_1'=e_1^r\ mod\ p$

2) $C_2'=e_2^r*m'\ mod\ p$

$\therefore {C_2\over C_2`}={{e_2^rm\ mod\ p}\over {e_2^rm'\ mod\ p}}$

attacker가 m를 알고 동일한 r값이 쓰였다면 m'을 알게 되는 것과 같아지기 때문에 Elgamal은 KPA 공격에 안전하지 않다.

1. RSA 알고리즘 개요

공개키 암호에는 대표적으로 RSA 암호가 일반적으로 사용된다. 하지만 RSA 알고리즘의 경우 수학적으로 안정성이 검증되지 않았고, 취약점이 나올 경우 거기에 맞춰 알고리즘을 수정하는 방식을 사용한다고 한다. 기본적으로 RSA 알고리즘은 같은 메시지에 대해서 같은 암호문을 생성하는 결정적인 특징을 가진다. 이를 방지하고자 확률적인 특징을 가지도록 하기 위해 고정패딩과 랜덤패딩을 붙이는 RSA-OAEP 방식을 사용한다. RSA-OAEP는 RSA 알고리즘의 취약점 중 하나인 CCA(선택암호문공격)에 안전하다는 것이 특징이다. RSA 암호이외에도 레빈 암호 시스템이 있다. 이는 수학적으로 안정성이 검증되었고 RSA보다 뛰어난 것으로 판단되었지만 RSA 암호보다 유명세를 타지 못해 별로 사용되지 않는 것이라 한다.

2. RSA 알고리즘

절차

(1) 서로 다른 두 소수 $p, q$를 선택
(2) $p$와 $q$를 곱하여 $n=p*q$를 계산
(3) $\phi(n) = (p-1)(q-1)$을 계산
(4) $1<e<\phi(n)-1$의 범위에서 공개키 $e$를 선택
(5) $d=e^{-1}\ mod\ \phi(n)$을 통해 비밀키 $d$를 계산
——————————
public key = $(n, e)$
private key = $(d)$
검증키 = $(n,e)$
서명키 = $(d)$

암호화 (Encryption)

$C \equiv m^e\ mod\ n$

복호화 (Decryption)

$m \equiv C^d\ mod\ n$

서명 (Signing)

$S \equiv H(m)^d\ mod\ n$ // $H()$ is hash function

검증 (Verification)

check if $S^e \equiv H(m)\ mod\ n$

$S^e \equiv (H(m)^d)^e\equiv H(m)$

= $m$과 $s$가, 검증키 $(e,n)$을 이용하여 $s^e\ mod\ n = m$이 되는지 확인.

3. RSA 알고리즘에 대한 선택암호문공격

1. $c = m^e\ mod\ n$이 주어짐.

2. 공격자는 $gcd(r,n)=1$이면서 $r\in(0,n-1)$을 선택

3. 공격자는 공개키 r을 이용하여 암호화하여 $c^*\equiv\ r^ec\ mod\ n$을 생성

4. 복호화 오라클로 전송하여 $c^{*d}\equiv\ ({r^ec})^d\ mod\ n$을 받음

5. $c^{*d}\equiv\ rc^d\ mod\ n$

6. $c^{*d}\equiv r(m^c)^d\ mod\ n$

7. $c^{*d} \equiv\ rm\ mod\ n$

8. $c^{*d}r^{-1} \equiv m\ mod\ n$을 통해 m을 구할 수 있음. 공격자는 자신이 선택한 r에 대응하는 역원
을 곱하면 됨.

현대암호학에서 사용되는 블록 암호 운용 방식은 크게 5가지가 존재한다.

5가지를 확인하기 이전 핵심에 대한 이해를 위한 키워드는 다음과 같다.

Keyword: 개념, 암호화, 복호화, 장단점, 블록재사용, 병렬처리, 에러전파

1. ECB(Electronic Code Book)

ECB는 운용모드중 가장 간단한 형태로 암호화와 복호화가 독립적으로 이루어진다. 때문에 병렬처리가 가능하다는 장점이 있다. 반면 블록의 암호화와 복호화에 사용하는 키가 같기 때문에 같은 평문에 대해 같은 암호문이 나온다는 단점이 있다. 때문에 블록재사용과 같은 취약점이 발생할 수 있다. 암호문 생성 또는 전송 중에 에러가 발생할 수 있다. 이러한 에러에 있어서 ECB는 독립적으로 암복호화되기 때문에 다른 블록으로 에러가 전파되지 않고 에러가 발생한 블록만 영향을 받는다.

2. CBC (Cipher Block Chaining)

CBC 운용모드는 ECB 운용모드의 취약점을 극복하기 위해 나온 것이다. 한 블록의 평문을 암호화하기 이전에, 이전의 평문이 암호화된 암호문과 XOR 연산을 하는 것이 특징이다. 맨 앞의 블록의 경우 이전의 암호문이 없기 때문에 IV (Initial Vector)를 사용하여 랜덤 초기화를 하는 것이 특징이다. CBC의 경우 암호화때는 병렬처리가 불가능하지만 복호화시에는 병렬처리가 가능하다. 에러전파의 경우 복호화시 암호문 $C_1$에 에러가 발생하면 $P_1$, $P_{i+1}$블록에 영향을 미치고 $P_{i+2}$블록 부터는 자기 복구(self recovering)을 통해 올바르게 동작한다.

3. CFB (Cipher FeedBack)

CFB 운용모드는 블록암호를 스트림암호로 변환한다. 평문과 이전 암호문이 암호화된 값과 XOR 연산을 통해 암호문이 생성된다. 초기에는 IV 값을 암호화하고 평문과 xor하여 암호문을 생성하는 것이 특징이다. CFB 운용모드는 평문과 암호문의 길이가 같아 별도의 정수배를 맞추는 패딩이 필요하지 않다. 복호화시에는 암호문을 알고있다는 가정하에 병렬처리가 가능하다. 에러전파는 CBC와 마찬가지로 암호문에 에러가 발생하면 해당 암호문에 해당하는 평문과 다음 평문에 영향을 미치게 되는 것이 특징이다.

4. OFB (Output FeedBack)

OFB 운용모드는 블록암호를 스트림암호로 변환한다. 평문과 암호문의 길이가 같아 패딩이 필요하지 않다. 동작 방식은 이전의 암호화된 값이 다시 암호화되어 평문과 XOR하여 암호문을 만들어낸다. 초기에는 IV 값을 암호화하여 평문과 다시 XOR한 뒤 암호문을 생성한다. 암호화와 복호화 과정이 동일하다는 특징을 가진다. OFB 모드에서는 평문과 관계없이 암호 알고리즘을 미리 돌려 XOR하기 위한 키스트림을 준비할 수 있는 것이 특징이다. 암호문에 1비트의 문제가 발생하면 대응되는 평문에 1비트의 에러가 발생한다.

5. CTR (CounTeR)

CTR 운용모드는 평문과 암호문의 길이가 같아 패딩이 필요하지 않다. 암호화와 복호화과정이 동일하다. 임의로 순서로 암호화와 복호화가 가능하다. Nonce와 Counter를 암호화하고 평문과 XOR하여 암호문을 만드는 것이 특징이다. 동일한 비밀키와 IV를 반복하여 사용할 경우 안전성에 문제가 생길 수 있다. 이러한 과정은 독립적으로 진행되어 병렬처리가 가능하다는 것이 특징이다. 암호문에 1비트의 문제가 발생하면 대응되는 평문에 1비트의 에러가 발생한다. EBC 모드 처럼 한 블록에서 생긴 에러가 다음 블록으로 전파 되지 않는다.

1. 기약 잉여계, 완전 잉여계, 오일러 함수 정의

기약 잉여계

• $\{a_1, a_2, \dots , a_m \}$가 법 $m$에 대한 완전 잉여계일 때, 여기서 $m$과 서로소인 원소만 모은 집합을 법 $m$에 대한 기약잉여계라 한다.

완전 잉여계

• $\{a_1, a_2, \dots , a_m \}$에서 $a \equiv a_i \pmod{m}$인 $a_i$가 유일하게 있을 때, $\{a_1, a_2, \dots , a_m \}$ 를 완전잉여계라고 한다.

오일러 정의

기약 잉여계 개념은 정수론에서 오일러의 정의를 증명하는 데 사용된다. 정수론에서 유용하게 쓰이는 정리로, 합동식과 관련이 있다. 페르마의 소정리를 일반화한 것이다.

• $a$와 $n$이 서로소인 양의 정수일 때, $a^{\varphi(n)} \equiv 1(mod\ n)$이다.
  • 여기서 $\varphi(n)$은 $1$부터 $n$까지의 정수 중 $n$과 서로소인 정수의 개수이다. 오일러 피 함수라고도 불린다.

• 양의 정수 $m$에 대하여, $m$ 이하의 자연수 중에서 $m$과 서로소인 정수의 개수를 $\varphi (m)$으로 나타내고 함수 $\varphi : Z→N$ 를 오일러의 $\varphi$ 함수라고 한다.
  
  • $\varphi$ = varphi

2. 확장 유클리드 알고리즘으로 곱셈의 역원 구하기

정의

유클리드 호제법이란 두 정수 사이에 최대공약수(GCD)를 보다 효과적으로 구하는 것으로, 인류 최초의 알고리즘이라 한다. 

두 개 자연수 $A, B$가 있고 $A\ \%\ B = r$이면 다음과 같다. (단, $A > B$)

$GCD(A,B) = GCD(B,r)$

이 때, $A\ \%\ B = r$에 의해 다음과 같은 식이 기본적으로 유도된다.

$A = Bq + r$

증명

두 자연수 $A,B (A > B)$의 최대공약수를 $G$라 하자. $G$는 공약수이므로 두 서로소 $a, b$에 대해 다음 식이 성립한다.

$A = aG, B = bG$

위의 식을 사용하여 $A = Bq + r$에 대입하면 다음과 같다.

$aG = bGq + r$

$r = aG - bGq$

$ r = (a - bq)G$

$A = aG, B = bG$에서 $a, b$가 서로소라면 $G$가 최대공약수이기 때문에 $b, a - bq$가 서로소임을 증명하면 된다.

이를 증명하기 위해서는 가정에 모순을 확인하는 귀류법을 사용하여 해결할 수 있다.

$b$와 $a - bq$가 서로소가 아니라면 두 수는 공약수 $k$를 가지기 때문에 다음과 같이 나타낼 수 있다.

$a - bq = mk$

$b = nk$

위 식의 항을 옮기고 대입하여 정리하는 과정은 다음과 같다.

$a = mk + bq$

$a = mk + nkq$

$a = (m+nq)k$

따라서 다음과 같은 식을 확인할 수 있다.

$a = (m+nq)k$

$b = nk$

하지만 $a$와 $b$는 서로소이나 공약수 $k$를 가지므로 거짓 명제이다.

따라서 $a-bq$와 $b$는 서로소이다.

3. 군환체 조건 정의 및 다항식체 모듈러 계산

군, 환, 체의 경우 대수학에서 사용되는 개념으로 기본적이면서 가장 중요한 개념으로 여겨진다.

군 환 체 정의

군

공집합이 아닌 집합 G 위에 다음 세 조건을 만족하는 이상연산 $\circ$가 정의될 때 $<G, \circ>$를 군이라 한다.

군의 공리

• 결합법칙 : $G$의 임의의 원소 $a, b, c$에 대해 다음이 성립한다.
  • $(a \circ b)\ \circ \ c\ =\ a\ \circ \ (b \circ c)$

• 항등원 : $G$의 모든 원소 $a$에 대해 다음이 성립하는 $e \in G$가 존재해야하며, 이 때 $e$를 $G$의 단위원 또는 항등원이라한다.
  • $a \circ e\ =\ e\circ a = a$

• 역원 : $G$의 각 원소 $a$에 대해 다음이 성립하는 $a^{-1}$이 $G$에 존재해야 하며, 이 때 $a^{-1}$를 $a$의 역원이라한다.
  
  • $a \circ a^{-1} = a^{-1} \circ a = e$

• 닫힘 : 어떤 집합의 임의의 두 원소(순서쌍)간에 연산이 행해질 때, 그 결과 역시 그 집합의 원소가 되는 것을 의미한다.
  • $a \circ b$ 연산의 결과도 집합 $G$에 속하며 순서쌍 $(a,b)$들의 곱(카테시안 곱) 연산에 대해 닫혀있음

군은 결합법칙, 항등원, 역원, 닫힘의 네 가지 특성을 가지고 있어야 한다.

군의 종류

• 가환군 or 아벨군
  • 군의 네 가지 특성에 추가적으로 교환법칙까지 성립할 경우 이를 아벨군(abelian group) 또는 가환군(commutative group)이라 한다.

• 순환군(Cyclic Group)
  
  • 한 원소로 군의 모든 원소를 표시할 수 있는 군을 의미하며, 이 때 해당 원소를 생성원(generator)라 한다.

• 덧셈군(Additive Group)
  
  • 군의 이항 연산이 덧셈 연산인 군

• 곱셉군(Muliplicative Group)
  
  • 군의 이항 연산이 곱셈 연산인 군

• 부분군(Subgroup)
  • 군 $G$의 부분집합으로 군 $G$와 같은 연산 구조를 가지는 군

군의 표기

• $(G, \circ)$ 또는 $<G, \circ>$ 또는 ${G, \circ}$
  • $G$: 군의 원소 집합
  • $\circ$ : 군의 연산
• 군의 차수/위수(order): $|G|$ 또는 $O(g)$ 또는 $G_n$ 또는 $ord(G)$로 나타낼 수 있다.

환

어떤집합 R 및 그 집합 위에 2개의 이항연산$(+, \circ)$이 정의되는 대수 구조를 의미하며 다음과 같이 표기한다.

• $(R, +, \circ)$ 또는 $< R, +, \circ>$ 또는 $환 R$

환의 공리

• 덧셈 연산에 대해 : $(R, +)$는 가환군
  • 닫혀 있음
  • 항등원(`0`)이 존재 $\rightarrow a + 0 = 0 + a = a$
• 각 성분에 대해 역원이 존재함$\rightarrow a + (-a) = (-a) + a = 0$

• 모든 성분에 대해 교환법칙이 성립 $\rightarrow a + b = b + a$

• 모든 성분에 대해 결합법칙이 성립 $\rightarrow (a + b) + c = a + (b + c)$

• 곱셈(\circ) 연산에 대해 : $(R, \circ)$
  • 닫혀 있음
  • 모든 성분에 대해 결합법칙이 성립 $\rightarrow (a\circ b)\circ c = a\circ (b\circ c)$
• 덧셈 및 곱셉 연산에 대해 : $(R, +, \circ)$
  • 모든 성분에 대해 분배법칙이 성립 $\rightarrow a\circ (b + c) = a\circ b + a\circ c, (a + b)\circ c = a\circ c + b\circ c$

추가적인 조건에 따른 환의 종류

• 가환환
  • 추가적으로 곱셈(\circ)에 대해서 가환이 되는 환 : $a \circ b = b \circ a)$

• 단위원을 갖는 환(Ring with Unity)
  • 추가적으로 곱셈 항등원 즉, 단위원을 갖는 환 : $1 \circ a = a \circ 1 = a$

• 나눗셈환
  • 단위원 1을 갖는 환으로써, 곱셈 역원이 존재하는 환 : 각 원소 $a \in R, a \neq 0$에 대해, $a \circ a^{-1} = a^{-1}\circ a = 1$

• 정역(Integraldomain)
  • 단위원 1을 갖는 가환환으로써, 추가적으로 다음 조건을 만족
    • $a \neq 0, b \neq 0$이면 $a \circ b \neq 0$을 만족함 또는
    • $a \circ b = 0$이면, $a = 0$ 또는 $b = 0$ $(a,b \in R)$

체

• 코드(부호) 등을 기술하는데 사용될 수 있는 수학적 대수 구조
  • 예) 실수 $R$, 유리수 $Q$, 복소수 $C$와 같은 수 체계에 대한 추상화
• 특정한 성질을 만족하는 2개의 연산이 정의되는 가환환
  • 그 요소들이 집합을 이루면서, 덧셈과 곱셈 연산 두 쌍을 사용할 수 있는 구조(2개 산술연산자)

체의 공리

• 덧셈 연산에 대해 : $<F, +>$
  • 집합 내 원소의 연산 결과가 다시 그집합 내에 있게된다. $\rightarrow$ 닫혀있음
  • 항등원 (`0`)이 존재 : $a + 0 = a = 0 + a$
  • 모든 성분에 대해 덧셈 역원이 존재 : $a + (-a) = 0 = (-a) + a$
  • 모든 성분에 대해 결합법칙이 성립 : $(a + b) + c = a + (b + c)$
  • 모든 성분에 대해 교환법칙이 성립 : $a + b = b +a$
• 곱셈 연산에 대해 : $<F, \circ>$
  • 모든 성분에 대해 분배법칙이 성립 : $a (b +c) = a b + a c$

위 체의 공리에서 덧셈 공리들 만을 만족할 경우는 아벨군 또는 가환군이며, 곱셈의 역원 존재 만을 제외한 나머지 공리들을 만족하는 경우는 환이다.

체의 공리가 성립하는 예제

• 실수체 : 실수 전체의 집합
• 복소수체 : 복소수 전체의 집합
• 유리수체 : 유리수 전체의 집합

유한개의 원소를 갖는 체 $\rightarrow$ 유한체(갈로이스체)

4. 중국인 나머지 정리

개요

중국인의 나머지 정리의 경우 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이며 그 기원은 다음과 같다.

중국의 5세기 문헌인 『손자산경(孫子算經)』에는 다음과 같은 문제가 있다고 한다.

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?

정의

$gcd(n,m) = 1$면 $\begin {cases} x \equiv b\ (mod\ n) \\ x \equiv c\ (mod\ m) \end {cases}$는 $1 \leq x \leq nm$에서 단 하나의 해를 갖는다.

증명

$x \equiv b\ (mod\ n)$    (1)

$x \equiv c\ (mod\ m)$    (2)

$x \equiv b\ (mod\ n)$이므로 $x = ny + b$를 만족하는 $y \in Z$가 존재할 것이고, 이를 (2)에 대입하면 다음과 같다.

$ny \equiv c -b\ (mod\ m)$

위 정의에 의해 위 합동식은 $1 \leq y \leq m$에서 유일한 해 $y_0$를 갖고, 따라서 $x = ny_0 + b$는 $1 \leq x \leq nm$에서 유일한 해 $x_0$를 가진다. 따라서 다음과 같다.

$x_0 = ny_0 + b$

여기서 $x_0$는 (1)의 해다. 이제 $ny_0 \equiv c -b\ (mod\ m)$에 $ny_0 = x_0 - b$를 대입하면 다음과 같다.

$x_0 \equiv c\ (mod\ m)$

$x_0$은 (2)의 해가 된다. 증명 끝.

5. 가우스 소거법 / 가우스 조단 소거법

가우스 소거법을 이용하여 연립 방정식의 해를 구하는 과정이며, 아래에서 $R_2$는 2열을 의미한다.