h32j00

다른 분들은 배열을 이용해서 풀었길래 카운트만 가지고 풀어봤습니다.

고려할 점

1. '('을 입력받을 때는 아무조건없이 카운트를 센다.

2. ')'을 입력받을 때는 '('의 카운트값과 비교해서 카운트를 센다. 

   --> 즉, 현재 입력받은 괄호 중에서 여는 괄호보다 닫는 괄호가 많아버리면 그 자리에서 반복문을 끝내고 NO를  출력하게 된다.

다음은 C언어로 작성한 코드입니다.

#pragma warning(disable : 4996)
#include <stdio.h>

int main()
{
	int T;
	char input[51];
	int i, j, o_cnt = 0, c_cnt = 0;
	scanf("%d", &T);
	for (i = 0;i < T;i++) {
		scanf("%s", input);
		for (j = 0;j < strlen(input);j++)
		{
			if (input[j] == '(') o_cnt++;
			else {
				if ((c_cnt + 1) <= o_cnt) c_cnt++;
				else { c_cnt = -1;break; }
			}
		}
		if (o_cnt == c_cnt) printf("YES\n");
		else printf("NO\n");
		o_cnt = 0;
		c_cnt = 0;
	}
}

다른 풀이법(스택 이용)

1. 입력받은 '('을 스택에 push한다.

2. ')'가 입력받아지면 스택에서 '('를 pop한다.

3. 입력이 끝나고 스택이 비어있지 않으면 "NO"를 출력한다. (VPS라면 스택의 모든 '('가 pop되어야 정상이기 때문)

처음에는 그냥 이중 포문 써서 했는데 시간 초과가 되는 바람에 다시 한번 생각을 해봤습니다.

고려해야할 조건은

1. 정수의 범위 - int 대신 double 사용

2. time limit - 이중포문 대신 qsort(), 이진 탐색 사용

다음은 C언어로 작성한 코드입니다.

#pragma warning(disable : 4996)
#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b)
{
	double ra = *(double*)a;
	double rb = *(double*)b;
	return ra - rb > 0 ? 1 : -1;
}

int main()
{
	double * a, * b;
	int n, m;
	int i, flag = 0;
	int l, r, mi;
	scanf("%d", &n);
	a = (double*)malloc(sizeof(double) * n);
	for (i = 0;i < n;i++) scanf("%lf", &a[i]);
	scanf("%d", &m);
	b = (double*)malloc(sizeof(double) * m);
	for (i = 0;i < m;i++) scanf("%lf", &b[i]);
	qsort(a, n, sizeof(double), compare);
	for (i = 0;i < m;i++) {
		l = 0;
		r = n - 1;
		while (1)
		{
			if (l <= r) {
				mi = (l + r) / 2;
				if (b[i] == a[mi]) { flag = 1;break; }
				else if (b[i] < a[mi]) { r = mi - 1; }
				else if (b[i] > a[mi]) { l = mi + 1; }
			}
			else break;
		}
		if (flag == 1) printf("1\n");
		else printf("0\n");
		flag = 0;
	}
    free(a);
    free(b);
}

배운 점

1. 문제의 조건을 잘보자.

2. qsort() 잘 사용하자.

3. 이진탐색

C언어를 이용하여 코드를 작성하였다.

처음 코드에는 정렬을 할 때, O(n^2)인 정렬을 써서 시간 초과가 나서 검색해보니 

stdlib.h 파일에서 제공하는 qsort()라는 함수를 발견하여 qsort()함수를 이용하여 코드를 작성하였다.

#pragma warning(disable : 4996)
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int len;
	char str[51];
}words;

int compare(const void *a, const void *b) {
	words real_a = *(words*)a;
	words real_b = *(words*)b;
	int len_a = strlen(real_a.str);
	int len_b = strlen(real_b.str);
	if (len_a != len_b)
		return (len_a - len_b);
	return strcmp(real_a.str, real_b.str);
}

int main()
{
	words* word;
	words tmp;
	int flag = 0, real_n = 0;
	char strtmp[51] = {0};
	int n, i, j;
	scanf("%d", &n);
	word = (words*)malloc(sizeof(words) * n);
	for (i = 0;i < n;i++)
	{
		scanf("%s", strtmp);
		for (j = 0;j < i;j++) {
			if (strcmp(word[j].str, strtmp) == 0) {
				flag = 1;
				break;
			}
		}
		if (flag == 0) {
			strcpy(word[real_n].str, strtmp);
			word[real_n].len = strlen(strtmp);
			real_n++;
		}
		flag = 0;
	}
	qsort(word, real_n, sizeof(words), compare);
	for (i = 0;i < real_n;i++) printf("%s\n", word[i].str);
	free(word);
	return 0;
}

입력을 받으면서 이전에 입력 받았던 문자열이면 배열에 추가하지 않게 설정하였다.

qsort()를 사용하기 위해서는 어떤 방식으로 sort를 할 것인지에 대한 함수가 추가적으로 필요한데 여기서는 compare()를 추가적으로 사용하였다.

Compare()

int compare(const void *a, const void *b) {
	words real_a = *(words*)a;
	words real_b = *(words*)b;
	int len_a = strlen(real_a.str);
	int len_b = strlen(real_b.str);
	if (len_a != len_b)
		return (len_a - len_b);
	return strcmp(real_a.str, real_b.str);
}

compare 함수만 따로 살펴보자.

문제에서 요구한 것을 다시 생각해보면 a,b를 비교할 때, 길이가 다르면 (예를 들어 i, no) i가 우선순위가 더 높다. (길이가 짧으니까!!)

우선순위가 높은것이 더 작은 수라고 생각하면 된다.

(음.. 1과 2가 있을때, 우선순위가 1이 먼저지만 수는 1이 더 작은 느낌이랄까)

그래서 len_a - len_b가 음수가 나올것이고 그건 a가 우선순위가 더 높다는 것을 뜻한다. (반대의 경우, 즉 길이가 긴 것이 우선순위가 높을 때에는 len_a - len_b가 양수이기 때문에 우선순위가 낮으니까 (-1)을 곱해준 뒤 return 하면 된다.)

길이가 같을 때에는 사전 순으로 배열이기 때문에 strcmp()함수를 써서 return을 하게 해주었다.

strcmp()은 a,b를 비교해서 a가 작으면 음수를 리턴하기에 딱 알맞게 사용했다고 볼 수 있다.

배운점

1. qsort() 함수를 처음 봤다. 종종 사용해야겠다.

2. 퀵정렬과 힙정렬도 생각해봐야겠다....... 먼 미래에..

문자열에 관련된 문제입니다. 

맨 처음 문자열(예시로 하면 config.sys)을 기준으로 다음 문자열과 비교하여 다르면 '?'로 문자를 바꾸는 식으로 코드를 작성하였습니다.

C를 이용하여 코드를 작성하였습니다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(void)
{
    int n, i, j, len;
    
    char a[50][51] = {0};
    char answer[51] = {0};

    scanf("%d", &n);

    for (i = 0; i < n; i++)
        scanf("%s", a[i]);

    len = strlen(a[0]);

    memcpy(answer, a[0], len);

    for (i = 0; i < len; i++)
    {
        for (j = 0; j < n - 1; j++)
        {
            if (a[j][i] != a[j + 1][i])
            {
                answer[i] = '?';
                break;
            }
        }
    }

    printf("%s", answer);

    return 0;
}

배운점

1. 학교에서 항상 void main()으로 했었는데 이것 때문에 컴파일에러가 났다. 컴파일러에 따라 컴파일에러가 난다고 하니 이제는 int main()으로 써야겠다.

이번 학기에 학교에서 프로젝트 중 ESGAN 모델을 써야하는 프로젝트가 있어서 ESGAN을 사용하다가

삽질을 8328483번 정도 했다.

나중을 위해서 후기를 써보겠다.

1. git clone github.com/open-mmlab/mmsr.git

2. 사전작업

training 시키기 전에 install 해줘야 할 것들을 다 해주자

3. dataset 전처리 과정

https://github.com/open-mmlab/mmsr/blob/master/datasets/DATASETS.md

위 링크에서 시키는 대로 dataset를 가공해야한다..

안그러면 tensor shape error 같은게 뜬다..

물론 mmsr이 제공하는 dataset으로 하면 문제 없지만 나처럼 다른 dataset을 가지고 학습을 진행한다면 가공을 해야한다!!!

- 쉽게 정리

1) GT  image 준비 - 해상도 좋은 이미지

2) 그 와 이름이 같은 LR image 준비 - 해상도 낮은 이미지 -> data_scripts/generate_mod_LR_bic.py 파일을 이용하여 만드는 것을 추천..

3) 이미지를 crop하기

4) LMDB file 만들기 

5) 테스트 해보기

위 과정들을 완료하여야 training을 진행할 수 있다.

4. pretrain model 준비

https://drive.google.com/drive/folders/17VYV_SoZZesU6mbxz2dMAIccSSlqLecY 

위 링크에서 pre-trained 모델을 다운받을 수 있다.

5. config 파일 수정

1) dataset 경로 수정하기

2) 진짜진짜 중요한거 -> gpu가 우리는 한개였는데 

gpu_ids: [3] 이거를 [0]으로 바꿔줘야한다.... 이거 때문에 2일을 꼬박 날렸다!!!!

6. training 해주기

github에서 하라는대로 training을 해주면 된다.

이와 같은 과정과 함께라면 별다른 에러없이 진행될 수 있다. 그럼 안농~

요즘은 문제를 풀면서 조금씩 지식을 쌓고있는 중이다.

오늘은 프리패치에 관한 문제를 풀었기 때문에 까먹지 않기 위해 프리패치에 대한 글을 하나 쓰려한다.

0. Prefetch file이란?

응용 프로그램이 특정 위치에서 처음 실행될 때 Windows에서 사전 추출 파일 생성.

쉽게말하면 시스템에서 한번이라도 실행된 적이 있는 프로그램은 프리패치 파일을 생성한다. 이런 이유로 포렌식 수사관들에게는 좋은 아티팩트라고 할 수 있다.

생성되는 포맷이 있는데 CMD.EXE-ABCDEF.pf 이런식으로 프로그램이름-hash.pf 형식으로 생성된다.

여기서 hash값은 실행파일의 path의 hash값이라고 한다.

prefetch file들은 C:\Windows\Prefetch 에 존재한다.

1. Prefetch file 생성 이유는?

프리패치 파일을 생성하면 프로그램 로딩속도가 빨라진다고 한다. 또한 128개였나? 그 정도를 max로 둬서 넘으면 예전꺼는 지워지는 것 같다.

2. NTFS ADS에 관련된 pf file

ADS란 Alternate Data Stream의 약자로 file에서의 데이터 스트림을 의미한다.

NTFS에서는 다중의 데이터 스트림을 지원하는데  파일에 하나 이상의 데이터 스트림을 담을 수 있다는 뜻이다.

그래서 ADS를 이용하여 데이터를 숨길 수 있다.

만약 h32j00.txt의 ADS에 svchost.exe를 숨기고 svchost.exe를 실행시킨다고 하면?

svchost.exe의 prefetch file이 생성되지 않고 h32j00.txt와 같은 이름의 파일이 생성된다.

정~말 신기하다!!

[참조]

1.

https://www.magnetforensics.com/blog/forensic-analysis-of-prefetch-files-in-windows/

2. 

https://kali-km.tistory.com/entry/ADS

오늘은 ​해시 함수​에 대해서 알아보도록 합시다. 요즘 포렌식 공부를 시작하고 있는 데 포렌식에서도 해시값이 쓰여서 더 자세히 읽어 봤던 것 같네요!!

​

해시 함수(hash function)이 쓰이는 곳

: 디지털 서명(digital signature), 공개 키 암호화(public-key encryption), 무결성 검증(integrity verification), 메세지 인증(message authentication), 패스워드 보호(password protection), 키 합의(key agreement) 프로토콜과 기타 여러 암복호화 프로토콜

​

현실 세상에서의 용도

: 클라우드 저장 시스템에서 동일한 파일 식별 및 수정된 파일 검출

: Git에서 저장소 안의 파일들을 식별

: 호스트 기반 침입 탐지 시스템(host-based intrusion detection systems, HIDS)에서 수정된 파일 검출

: 네트워크 기반 침입 탐지 시스템(network-based intrusion detection systems, NIDS)에서 악의적인 자료가 네트워크로 유입되었는지 파악

: 디지털 법의학 분석가(forensic analyst)들은 디지털 증거물이 수정되지 않았음을 증명할 때

: 비트코인은 작업증명(proof-of-work) 시스템

​

핵심 내용!

*해시 함수의 보안성 - 충돌 저항성(collision resistance), 역상 저항성(preimage resistance)

*구조 - SHA-1, SHA-2, SHA-3, BLAKE2의 내부 구조

6.1 보안 해시 함수

암호의 목적 : 자료의 기밀성

해시 함수의 목적 : 자료의 무결성

​

6.1.1 다시 등장한 비예측성

보안 해시 함수의 해시 값들이 예측 불가이기 때문에 SHA-256("a"), SHA-256("b"), SHA-256("c") 값을 알고 있어도 SHA-256("d") 값을 예측 할 수 없다.

보안 해시 함수는 입력이 주어질 때마다 무작위한 비트열을 돌려주는 블랙박스와 같아야 한다.

​

6.1.2 역상 저항성

주어진 해시 값 H에 대해 Hash(M) = H를 만족하는 임의의 메세지 M을 역상(preimage)라고 함.

역상 저항성 : 어떤 무작위 해시 값이 주어졌을 때 공격자가 그 해시 값의 역상을 결코 찾아낼 수 없다는 보안 보장 속성.

실제로 해시 함수를 일방향 함수(one-way function)라고 부른다.

역상 저항성은 제1 역상 저항성과 제2 역상 저항성으로 나뉜다.

제1 역상 저항성(first-preimage resistance) : M을 찾을 수 없다.

제2 역상 저항성(second-preimage resistance) : 어떤 메세지 M1의 해시 값과 동일한 값을 산출하는 M2를 찾을 수 없다. // 메세지 M1, M2가 있을 때 같은 해시 값을 가질 수가 있는 데 이유는 정보의 양이 너무 많아서 충돌을 피할 수 없기 때문이다.

​

6.1.3 충돌 저항성

해시 값의 충돌은 앞서 말했던 것처럼 서로 다른 메세지들이 같은 해시 값을 내는 것 또는 그러한 메세지들을 말한다. -> 비둘기집 원리(pigeonhole principle) : m개의 구멍(비둘기 집)에 n마리의 비둘기를 집어넣을 때 m<n이면 적어도 하나의 구멍에는 두 마리 이상의 비둘기가 들어가게 된다는 것

충돌 저항성은 제2 역상 저항성 개념과 관련있음.

​

6.1.4 충돌 찾기

역상 찾는 데 : 2^n회의 연산

충돌 찾는 데 : 2^(n/2)회의 연산

즉 충돌 찾는 게 더 빠르다. -> 생일 공격(birthday attack) : N개의 메세지와 그만큼의 해시 값이 주어졌을 때, 두 해시 값의 쌍들을 점검해서 최대 N x (N-1) / 2개의 잠재적 충돌을 만들 수 있다.

​

*소박한 생일 공격 : 생일 공격으로 충돌을 찾는 가장 간단한 방법이지만 상당히 많은 메모리가 필요함

1. 2^(n/2)의 임의로 선택한 메세지들로 2^(n/2)개의 해시 값을 계산하고, 각 메시지-해시 쌍을 하나의 목록에 저장한다.

2. 그 목록을 해시 값을 기준으로 정렬한다. 그러면 해시 값이 같은 쌍들이 인접한 위치에 놓이게 된다.

3. 정렬된 목록을 훑어서, 해시 값이 같은 두 쌍을 찾는다.

-> 이러한 정렬에 평균 n2^n회의 기본 연산이 필요

​

*로 방법(Rho method) : 메모리를 조금만 사용하는 충돌 검색

1. n비트 해시 값을 산출하는 해시 함수가 주어졌다고 할 때, 무작위 해시 값 H1을 선택하고 H1=H1' 로 정의한다.

2. H2 = Hash(H1)과 H2' = Hash(Hash(H1')) 을 계산한다. 전자는 해시 함수를 한 번, 후자는 해시 함수를 두 번 적용

3. Hi+1 = H'i+1 을 만족하는 i에 도달할 때까지 i를 증가하면서 Hi+1 = Hash(H1), H'i+1 = Hash(Hash(H'i))를 반복

말로 하면 어려우니까 그림을 살펴보자

주목할 점은 충돌을 찾으려면 이러한 순환마디를 찾기만 하면 된다는 것이다.

-> 순환마디(cycle) : 쉽게 말하면 그림에서의 동그라미~

다수의 값을 메모리에 저장하거나 긴 목록을 정렬하지 않기 때문에 메모리를 많이 소비하지 않는다.

​

6.2 해시 함수의 구축

메시지를 해싱하는 가장 간단한 방법 : 메시지를 작은 조각들로 나누고 각 조각을 비슷한 알고리즘을 이용해서 연달아 처리하는 것 -> 반복 해싱(interative hashing)

반복 해싱에는 크게 두 종류가 있다.

1. 머클-담고르 구성 : 입력을 더 작은 출력으로 변환하는 압축 함수(compression function)를 이용한 반복 해싱

2. 스펀지 함수 (sponge function) : 입력을 같은 크기의 출력으로 변환하는 함수를 이용한 반복 해싱

​

6.2.1 압축 기반 해시 함수: 머클-담고르 구성

MD4, MD5, SHA-1, SHA-2 족 해시 함수들 모두 머클-담고르 구성(M-D)을 따른다.

완벽하지는 않지만, 간단할 뿐만 아니라 여러 응용에 대해 충분히 안전함이 증명되었다.

M-D 구성을 따르는 해시 함수는 메시지를 같은 크기의 여러 블록으로 나눈 후 그 블록들을 하나의 압축 함수를 이용해서 하나의 내부 상태와 함께 섞는다.

compress : 압축 함수

H0, H1, ... : 연쇄 값(chaining value)

내부 상태의 마지막 값이 해시 값이다.

​

*블록 채우기

해싱할 메시지가 블록 단위로 떨어지지 않는다면? 블록을 채워야한다.

M-D 구성은 마지막 블록을 다음과 같이 구축한다: 남은 비트를에 '1'을 하나 추가하고 남은 비트들에는 0개를 추가하고 마지막으로는 원래의 메시지의 길이를 부호화한 고정된 개수의 비트들을 추가한다.

예를 들자면 520비트 메시지를 해싱하면 512비트 블록 하나와 8비트가 남고 그 8비트가 10101010 이라고 하면 10101010 1 000 ... 000 1000 이렇게 채우는 것이다. 처음에 1 추가, 그다음 0을 개수 맞춰서 추가, 마지막은 8비트가 남았었으니까 8이라는 2진수 표현인 1000을 추가하는 것.

​

*보안성 보장

압축 함수의 보안성 -> 해시 함수의 보안성 보장 (역은 성립 X)

​

*압축 함수의 구축 : 데이비스-마이어 구성

SHA-256이나 BLAKE2 같은 실제 해시 함수에 쓰이는 모든 암축 함수는 블록 암호에 기초.

상자 상단의 검은 역삼각형은 블록 암호의 키가 입력되는 지점.

Hi = E(Mi,Hi-1) xor Hi-1

여기서 Mi가 블록 암호의 키로 쓰이고 Hi-1은 평문 블록으로 쓰인다.

​

6.2.2 치환 기반 해시 함수: 스펀지 함수

좀 더 단순한 구조의 해시 함수를​ 스펀지 함수라고 부른다.

압축 함수와 블록 암호 대신 하나의 치환 함수를 사용.

스펀지 함수는 블록 암호를 이용하여 내부 상태와 메시지 비트들을 섞는 대신 XOR 연산을 사용

스펀지 함수가 쓰이는 용도 : 결정론적 난수 비트 발생기, 스트림 암호, 의사난수 함수, 인증 암호

가장 유명한 스펀지 함수 : Keccak(케착!) -> SHA3 함수임

*스펀지 함수의 작동 과정

1. 첫 메시지 블록 M1과 H0을 XOR한다. 여기서 H0은 내부 상태의 미리 정의된 초기치이다. 메시지 블록들은 모두 같은 길이이며, 함수의 내부 상태보다 작다.

2. 치환 함수 P를 이용해서 내부 상태를 같은 길이의 다른 값으로 변환한다.

3. 둘째 블록 M2와 내부 상태를 XOR하고, 내부 상태에 다시 P를 적용한다. 이러한 과정을 나머지 블록에 반복한다. 이것을 흡수 단계(absorbing phase)라고 부른다.

4. 모든 메시지를 흡수 했다면, 다시 P를 적용한 후 내부 상태로부터 비트들의 블록을 추출해서 해시 값을 만든다. 이것을 압착 단계(squeezing phase)라고 부른다.

​

스펀지 함수의 보안성은 내부 상태의 길이와 블록들의 길이에 의존.

스펀지 함수가 안전하려면 치환 P가 무작위 치환처럼 행동해야 한다.

​

6.3 SHA족 해시 함수

SHA(Secure Hash Algorithm) 해시 함수들은 군(military)에 속하지 않는 미국 연방 정부 기관들이 사용하도록 NIST가 정한 표준들.

​

6.3.1 SHA-1

SHA-0에 대한 충돌을 2^80회가 아니라 약 2^60회의 연산으로 찾아내는 방법을 발견하면서 SHA-1 표준이 나왔다. 이후 2^33회의 연산으로까지 줄여버렸다.

​

*SHA-1의 내부

SHA-1은 특별히 만든 블록 암호(SHACAL)에 기초해서 머클-담고르 해시 함수와 데이비스-마이어 압축 함수를 결합한 것이다.

SHA-1의 compress, blockcipher, expand, f 함수 중 f 함수에서 비선형 & 연산자를 이용하여서 이 덕분에 차분 암호해독 공격이 방지된다.

SHA-1의 연쇄값은 160 비트.

​

*SHA-1에 대한 공격들

크롬 브라우저는 HTTPS 연결에 SHA-1을 사용하는 웹사이트를 '안전하지 않음'으로 표시한다. (처음알았음 ㅋㅋ)

SHA-1은 안전하지 않아서 사용하지 말아야 한다. -> 충돌 저항성 수준이 80비트였는 데 결함을 찾아서 2^63 회의 연산으로 충돌을 찾을 수 있게 되었다.

​

6.3.2 SHA-2

NSA가 설계하고 NIST가 표준화했다.

SHA-224, SHA-256, SHA-384, SHA-512로 이루어져있다.

​

*SHA-256

SHA-256의 연쇄값은 256비트이다. 메시지 블록은 512 비트로 SHA-1과 동일하다.

메시지 확장 함수 expand256()이 쓰이는 데 SHA-1의 expand()보다 복잡하다.

SHA-1 expand() : xor와 1비트 회전 수행

SHA-256 expand256() : xor, and, 회전 수행.

SHA-256은 256비트의 역상 저항성을 보장하고 있다.

​

*SHA-512

SHA-512의 연쇄값은 512비트이다. 메시지 블록은 1024비트이다.

회전 거리 빼고 SHA-256과 거의 같다.

약 256비트의 충돌 저항성을 보장한다.

​

혹시나 SHA-2에 대한 공격 기법이 나타날지도 모른다는 대비책으로 NIST는 SHA-3을 개발했다.

​

6.3.3 SHA-3 공모전

요구 조건 : SHA-2만큼 안전하고 빠르고 SHA-2가 할 수 있는 일은 모두 할 수 있어야 한다. SHA-1, SHA-2와는 다른 구조여야 한다.

최종적으로 Keccak 이 우승작이 되었다.

NIST : "Keccak 은 설계가 우아하고, 보안 이득이 크고, 전반적인 성능이 좋고, 하드웨어 효율성이 탁월하고, 유연성도 훌륭하다."

​

6.3.4 Keccak ( SHA-3 )

스펀지 함수의 일종인 Keccak의 핵심 알고리즘은 1600비트 상태를 치환해서 1152비트나 1088비트, 832비트, 576비트 블록들을 처리하며, 그 결과로 224, 256, 384, 512 비트의 해시 값을 산출한다.

하나의 핵심 알고리즘을 사용해서 네 가지 길이의 해시 값들(224,256,384,512)을 모두 생성한다.

SHA-3 표준 명세서 FIPS 202에는 두 가지 알고리즘 SHAKE128, SHAKE256이 정의되어 있다.

이 두 알고리즘은 확장 가능 출력 함수(extendable-output function, XOF)라고 부른다. -> 가변 길이의 해시 값들을 산출할 수 있는 해시 함수이다.

​

표준 명세서 자체가 너무 길고 어려워서 tiny_sha3 이라는 구현 코드를 읽는 게 더 쉽다.

tiny_sha3은 Keccak의 치환 P를 구현하는 데 이 함수가 하나의 라운드를 여러번 수행한다.

하나의 라운드는 4개의 단계로 이루어져 있다.

1. Theta : 64비트 워드들의 XOR와 워드들의 1비트 회전이 포함

2. Rho Pi : 64비트 워드들의 회전이 포함 ( 회전 자릿수는 Keccakf_rotc[] 배열에 고정 )

3. Chi : XOR와 AND도 적용 -> 유일한 비선형 연산들

4. Iota : Keccakf_rndc[] 에 미리 고정된 64비트 상수와의 XOR 수행

​

6.4 BLAKE2 해시 함수

해시 함수에서 중요한 것 : 보안성 그리고 속도! 속도도 무시할 수 없는 요인

SHA-3 공모전 이후 나온 BLAKE2라는 해시 함수의 설계자들이 설계 시 염두에 둔 사항

: SHA-3만큼은 안전해야 한다.

: MD5를 비롯한 기존의 모든 해시 표준보다 빨라야 한다.

: 현대적인 응용들에 사용하기에 적합해야 하며, 대량의 자료를 해싱할 수 있어야 하며, 비밀 키를 지원하되 비밀 키 없이도 해싱 할 수 있어야 한다.

: 다중 코어 시스템에서 현대적인 CPU의 병렬 컴퓨팅 지원 기능은 물론이고 단일 코어 안의 명령 수준 병령성을 활용하기에도 적합해야한다.

-> BLAKE2b, BLAKE2s가 만들어졌음. 전자는 64비트 플랫폼 최적화, 후자는 8~32비트 플랫폼 최적화이다.

BLAKE2의 압축함수는 데이비스-마이어 구성의 한 변형으로 카운터(counter), 플래그(flag)라는 추가적인 매개변수를 받는다.

카운터 : 압축 함수의 각 실행이 매번 다른 함수처럼 행동하게 만드는 역할

플래그 : 압축 함수가 마지막 메시지 블록을 처리하는지의 여부 ( 보안성 높이기 위한 장치 )

압축 함수에 쓰이는 블록 암호는 스트림 암호 ChaCha(Salsa20의 변형)에 기초했다.

​

6.5 문제 발생 요인들

6.5.1 길이 연장 공격(length-extension attack)

머클-담고르 구성에 대한 주된 위협이 길이 연장 공격이다.

SHA-2 해시 함수는 길이 연장 공격에 취약하다.

이 공격은 마지막 압축 함수 실행을 이전의 모든 압축 함수 실행과 조금 다르게 만들기만 하면 해결된다. 방금 전 설명했던 BLAKE2에서 flag를 사용하는 것도 이러한 공격을 피해 보안성을 높이려는 것에 해당한다.

​

6.5.2 저장증명 프로토콜 속이기

클라우드 컴퓨팅 응용 프로그램들은 저장증명(proof-of-storage) 프로토콜(클라이언트가 저장해달라고 요청한 파일을 서버가 실제로 저장했음을 증명하는 데 쓰이는 프로토콜)안에서 해시 함수를 사용해왔다.

​

*저장증명 프로토콜

1. 클라이언트는 어떤 난수 값 C(시도, challenge라고 부른다)를 선택한다.

2. 서버는 그에 대한 응답(response)으로 Hash(M||C)를 계산해서 클라이언트에게 보낸다.

3. 클라이언트도 Hash(M||C)를 계산해서 그것이 서버가 보낸 응답 값과 일치하는지 확인한다.

​

만약 서버가 연쇄 값 H1=Compress(H0,M1)을 계산하고 M 자체를 폐기하면 Hash(M||C)를 계산하는 데는 아무 문제가 없지만 M을 사실상 저장하지 않고 클라이언트를 속일 수 있다.

​

이러한 문제의 해결책은 Hash(C||M)을 맞추어 보도록 하면 된다.

​

항상 헷갈렸던 두 친구를 다시 한 번 정리하고 가려한다.

- Little Endian

높높낮낮으로 외우면 아주 간단하다.

만약 HDD에 0xAABBCCDD가 저장되어 있다고 한다면

높은 자리 수가 높은 주소에 로드되는 것..

그럼 읽어오면 0xDDCCBBAA 이렇게 되는 것이다.

- Big Endian

얘는 Little Endian의 반대이다!! 많이 안쓰일 것 같지만 생각보다 자주 봐서 놀랍다..

똑같이 HDD에 0xAABBCCDD가 저장되어 있다고 하면 

높은 자리의 수(AA)부터 낮은 주소에 쓰기 시작한다.

이제 더 이상은 안 헷갈릴 것 같다!! 빠-끄