Linux Kernel Hacks: NanoPi R4S로 PQ-Wireguard VPN Router 만들기(Part II)

이번 시간에는 지난 시간에 이어 NanoPi R4S board를 가지고 PQC Wireguard 기반 초소형 VPN router를 만드는 과정(Part II)을 소개해 보고자 한다. 😎

목차
1. NanoPi R4S board 소개
2. OpenWrt build하기
3. WireGuard Kernel 코드 분석하기
4. CRYSTALS Kyber PQC 알고리즘 소개

5. NanoPi R4S 용 Quantum Safe WireGuard 구현하기

6. Alpine Linux 용 Quantum Safe WireGuard 구현하기

7. References

Keyword: NanoPi R4S, Intel AVX2, Alpine Linux, WireGuard, PQC, CRYSTALS Kyber

<Part I>

https://slowbootkernelhacks.blogspot.com/2023/02/nanopi-r4s-pq-wireguard-vpn-router.html

WireGuard는 정말로 잘 설계된 vpn protocol이다. WireGuard에 NIST 표준으로 지정된 CRYSTALS Kyber 알고리즘을 접목시킴으로써 양자컴퓨터 시대를 대비하는 새로운 vpn protocol을 만들어 보면 어떨까 ?

4. CRYSTALS Kyber PQC 알고리즘 소개
이번 장에서는 PQC 알고리즘 중 CRYSTALS Kyber의 세부 동작 과정을 분석해 보고자 한다. CRYSTALS Kyber 관련 많은 논문(paper)를 읽어 보았지만, 아래 논문이 가장 이해하기 쉬운 형태의 그림을 제공하고 있어서, 이번 장에서는 아래 논문을 기초로 CRYSTALS Kyber의 세부 동작 원리를 파헤쳐 보고자 한다. 이 자리를 빌어 아래 논문 저자에게 감사의 인사를 전한다. 😍

Active Implementation of End-to-End Post-Quantum Encryption, Anton Tutoveanu

a) CRYSTALS Kyber KEM 소개

CRYSTALS Kyber는 KEM(Key Encapsulation Mechanism)을 위한 PQC 알고리즘이다. KEM은 아래와 같이 3단계 과정 즉, Keypair 생성, Encapsulation 및 Decapsulation으로 구성되어 있다.

<KEM 절차 요약>

(1) Alice(Initiator)는 Key 쌍 (pk, sk)를 하나 만든 후, Bob(Responder)에게 pk(public key)를 전달한다.
(2) pk를 받은 Bob은 Enc(encapsulation) 함수를 이용하여 대칭키 ss와 ss를 암호화한 값 c를 만든 후, Alice에게 c 값을 전달한다.
(3) c 값을 수신한 Alice는 자신이 이미 가지고 있는 sk(secret key = private key)와 Dec(decapsulation) 함수를 이용해 대칭 키 ss를 획득한다.

이후, Alice와 Bob은 서로 공유하게 된 ss 값을 이용해 암호 통신(예: AES, ChaCha20 등)을 수행하게 된다.

[그림 4.1] PQC KEM 개요(1) [출처 - 참고문헌 11]

[그림 4.2] PQC KEM 개요(2) [출처 - 참고문헌 11]

b) CRYSTALS Kyber 알고리즘의 상세 동작 원리

CRYSTALS Kyber는 M-LWE(Module Learning with Errors) 문제에 기초하고 있는데, 알고리즘의 세부 구조를 앞서 설명한 3단계 과정을 기준으로 가볍게(?) 짚고 넘어 가도록 하자.

[그림 4.3] Learning with Errors [출처 - 참고문헌 11]

📌 위의 그림에서 vector B가 public key로 사용(matrix A는 public key를 만들기 위해 필요함)되고, vector s가 secret key(= private key)로 사용된다. Vector e는 작은 에러(noise) 값이다.

(1) Key 생성 과정

Public, Private key 쌍을 생성하기 위해 제일 먼저 해야 하는 일은 [그림 4.3]의 public matrix A, secret vector s 및 error(= noise) vector e를 만드는데 필요한 random seed 값을 생성하는 것이다. 먼저 32 byte random bytes에 대해 SHA3-512를 돌려 64bytes output(digest)를 생성한다. 64 bytes 중 앞의 32 bytes는 public seed(Matrix A 생성용)로, 나머지 반은 noise seed 값으로 활용된다.

[그림 4.4] CRYSTALS Kyber Seed 생성 과정[출처 - 참고문헌 11]

(설명 과정을 단순화하기 위해)Kyber768의 경우, A는 256길이 mod q 계수 배열을 포함하는 3x3 matrix(행렬)로, matrix의 각 항목을 생성하기 위해 앞서 생성한 public seed와 index 값 i, j를 기반으로 SHAKE-128을 돌린다. SHAKE-128을 통해 생성된 byte array는 다시 값을 수락 or 거부하는 sampling 함수를 거쳐 최종적으로 길이 256 다항식 mod q를 결과로 출력하게 되고, 이것이 matrix A의 (i, j) 값을 구성하게 된다. 캬~ 무슨 말인지 좀 어렵다.

[그림 4.5] CRYSTALS Kyber Public Matrix A 생성 과정[출처 - 참고문헌 11]

📌 SHAKE-128은 XOF(eXtendable Output Function)로, output 길이가 변할 수 있는 hash 함수이다.

Public matrix A가 만들어 졌으니, 이번에는 secret s vector와 noise e vector를 만들 차례이다. 2개를 만드는 방식은 동일한데, 먼저 [그림 4.4]에서 생성한 noise seed 값과 Nonce(정수이면서 매번 1씩 증가) 값에 대해 SHAKE-256을 돌려 128 bytes array를 만든다. 다음으로 128 bytes array를 1024 bits로 바꾼 후, CBD(centered binomial distribution - 중심 이항 분포) sampling를 한다. 그 결과 256 길이의 array를 얻을 수 있게 되고, 이는 secret s로 활용된다. noise e도 동일 과정을 통하여 생성한다.

[그림 4.6] CRYSTALS Kyber Secret & Noise 생성 과정[출처 - 참고문헌 11]

📌 CBD sampling은 쉽게 얘기해서 1024bits 내용에 대해 순차적으로 4bit 씩 묶어, {-2, -1, 0, 1, 2} 중의 하나로 줄이는 과정으로 이해하면 된다.

여기까지의 과정을 거쳐, matrix A, secret s vector, noise e vector가 만들어 졌으니, 이제 아래의 연산을 통해 pk 즉 public key를 만드는 것이 가능해졌다.

As + e = pk

As + e의 결과 값은 (n 차원 polynomial mod q) 1x3 vector 인데, 256 bytes인 각 항목을 encoding하여 384 bytes로 만든 후, 앞서 생성했던 public seed 32bytes를 이어 붙이면 아래와 같이 1184 bytes의 public key(Kyber 768 기준)가 만들어지게 된다.

384 x 3 + 32 = 1184 bytes

한편 Private key(= secret key)는 1x3 secret vector를 encoding 하여 384 bytes로 만든 후, 이들을 연결(concatenation)하여, 아래와 같이 1152 bytes로 완성되게 된다.

384 x 3 = 1152 bytes

[그림 4.7] CRYSTALS Kyber Public & Private Key 계산 과정[출처 - 참고문헌 11]

(2) Encapsulation 과정 및 (3) Decapsulation 과정

여기까지, 매우 험난한(?) 과정을 통해, public key와 private key(or secret key)가 만들어 졌다. 이제 Encapsulation(Encrypt) 과정과 Decapsulation(Decrypt) 과정을 소개할 차례이다.

먼저, Encrypt 과정을 위해서는 앞서 생성한 public key, 32bytes message(shared secret), 그리고 coin('0', '1'의 반복이 동전을 던져 앞면, 뒤면이 random하게 나오는 것과 유사해서 그렇게 부름)이라고 부르는 32bytes random byte array가 사용되고, 그 결과로 ciphertext 1088 bytes(Kyber 768 기준)가 생성된다.

Public key를 전달 받은 Bob은 random array r과 matrix A(정확히는 A의 전치 행렬) 및 e1을 이용해 1x3 vector u를 계산하고, r과 public key(정확히는 public key의 transpose), e2, 그리고 message m을 이용해 v 값을 생성해 낸다. 이 두개의 값 u + v를 한 것이 ciphertext가 된다.

📌 Ciphertext를 만들기 위해 단순히 u+v하는 것은 아니고, ciphertext size를 줄이기 위해 압축(compressing)과 하위 bit 일부를 정리하는 과정(?)을 거친다.

Alice's KeyGen( )

As + e = pk

Bob's Enc( )

r x A(t) x pk

+ e1 | e2

+ 0 | m

= u | v

위의 수식을 위에서 부터 아래로 줄줄이 계산해 보면, 아래와 같은 식을 얻을 수 있다.

r x A(t) + e1 = u

r x pk(t) + e2 + m = v

📌 r과 e1, e2는 앞서 설명한 noise sampling을 통해 생성한 값들이다.

📌 암호 연산 과정에는 곱셈 연산이 많이 등장하는데, 알고리즘 속도에 지대한 영향을 주는 부분이므로, Kyber에서는 NTT(Number Theoretic Transform)라는 기법을 사용하여 속도 문제를 해결하고 있다.

[그림 4.8] CRYSTALS Kyber Encapsulation 과정[출처 - 참고문헌 11]

한편, ciphertext (u, v)를 전달받아, message m(shared secret)을 구해내는 decapsulation 과정은 u, v 및 secret vector s를 통해 진행된다. 먼저, 전달 받은 ciphertext (u, v)에 대해 decoding과 decompressing을 한 후에 원본 message m을 아래 수식을 통해 구하게 된다.

Alice's Dec( )

v - (u x s(t)) = m + [x]

📌 [x]는 버리거나 올림할 수 있는 작은 값이다. 예를 들어, [3.4] => 버림 => [3], [3.6] => 올림 => [4] ...

아래 그림은 v - (u x ) = m + [x]의 수식의 원리를 설명해 주는 그림이다. 앞서 Bos's Enc( )에서 언급했던 수식을 참조하여 계산해 보면, u와 v의 관계가 설명될 줄로 믿는다. 😋

[그림 4.9] CRYSTALS Kyber Decapsulation 과정 중, u, v의 관계 [출처 - 참고문헌 12]

📌 위의 그림에서 t는 pk(public key)이다. 서로 다른 문서에서 발췌하다 보니 수식의 변수명이 좀 다르다.

[그림 4.10] CRYSTALS Kyber Decapsulation 과정[출처 - 참고문헌 11]

이상으로 조금은 난해하지만, CRYSTALS Kyber의 세부 동작 원리를 파악해 보았다. 설명이 부족한 부분에 대해서는 앞서 제시한 논문을 꼼꼼히 읽어 보기를 권한다. 공돌이가 수학을 이해하려니 조금 힘에 부친다. 😓

5. NanoPi R4S 용 Quantum Safe WireGuard 구현하기
이번 장에서는 CRYSTALS Kyber KEM을 WireGuard에 접목시키는 내용을 소개해 보고자 한다. 이 장에서 소개하는 내용은 아래 PQ-WireGuard 논문에서 영감을 받긴 했으나, 접근 방법을 좀 달리 하고자 하였다.

https://eprint.iacr.org/2020/379.pdf

WireGuard Protocol(NoiseIK) + CRYSTALS Kyber KEM

a) WireGuard에 Kyber KEM 추가하기

Wireguard에 CRYSTALS Kyber 알고리즘 적용 시, NoiseIK 프로토콜이 일부 변형될지라도, 속도 저하가 없는 방법이 필요하다. 아래 세 장의 그림은 CRYSTALS Kyber를 WireGuard Protocol에 녹이는 내용(idea)을 정리해 본 것이다.

📌 Noise Handshaking 중에 속도 저하가 발생하지 않도록 하기 위해서는 반드시 Initiation message와 Response message가 1번씩만 전송되도록 설계되어야 한다.

[그림 5.1] Quantum Safe WireGuard Protocol(1) - Kyber KEM 과정 추가

[그림 5.2] Quantum Safe WireGuard Protocol(2) - Handshake 메시지 변경

Kyber768의 public key size는 1184 bytes이고, ciphertext size는 1088 bytes이다. WireGuard의 Initiation Message의 size가 148 bytes, Response Message의 size가 92 bytes인 점을 감안할 때, 아무리 커져도 1332 bytes를 넘지 못하게 되고, 이 크기는 wireguard MTU 1420을 초과하지 않으므로, Initiation message와 Reponse message는 1번씩만 전송되게 된다.

[그림 5.3] Quantum Safe WireGuard Protocol(3) - Noise Protocol 변경

CRYSYALS Kyber KEM을 통해 획득한 shared secret은 NoiseIK(4번의 ECDH)를 통해 획득한 shared secret과 최종적으로 HKDF 함수(Blake2s 기반 hash 함수 사용)를 통해 다시한번 mix 되게 된다. 이는 Kyber를 통해 획득한 shared secret을 양자 computer로도 알아낼 방법이 없기 때문에, Post Quantum 시대에도 안전하다고 말할 수 있겠다. 이름하여 Hybrid WireGuard(= Quantum Safe WireGuard)~✌

Final Shared Secret = HKDF(NoiseIK result, Kyber KEM result)

b) Porting 절차 요약

Wireguard에 CRYSTALS Kyber KEM을 적용하기 위해 필요한 porting 절차를 정리해 보기로 한다. Porting을 위해 사용한 code는 PQClean이 되겠다.

https://github.com/PQClean/PQClean/crypto_kem/kyber768/clean

<porting 절차>

1) cd drivers/net/wireguard

2) Makefile을 수정하여 아래 내용을 추가한다.

ccflags-y += -O3 -fvisibility=hidden

ccflags-y += -Wframe-larger-than=2048

wireguard-y += kyber/clean/cbd.o

wireguard-y += kyber/clean/fips202.o

wireguard-y += kyber/clean/indcpa.o

wireguard-y += kyber/clean/kem.o

wireguard-y += kyber/clean/ntt.o

wireguard-y += kyber/clean/poly.o

wireguard-y += kyber/clean/polyvec.o

wireguard-y += kyber/clean/reduce.o

wireguard-y += kyber/clean/symmetric-shake.o

wireguard-y += kyber/clean/verify.o

wireguard-y += kyber/clean/kex.o

3) userspace용 C header를 제거하고, kernel header로 교체한다.

#include <stdint.h> => #include <linux/types.h>

#include <stddef.h>

#include <string.h> => #include <linux/string.h>

4) fips202.[ch] 파일을 common에서 복사해 온다. malloc/free code를 kmalloc/kfree code로 전환한다. exit 함수를 제거한다.

5) randombytes.h 파일을 common에서 복사해 온다.

6) [중요] local buffer size가 큰 경우, array 관련 코드를 kmalloc 등으로 교체한다. 이 작업을 안할 경우 system이 그냥 뻗어 버린다.

- stack buffer size 2048 이상의 경우 kmalloc으로 교체 검토

- indcpa.c의 keypair, enc, dec 3개 함수 polyvec, poly 부분 kmalloc으로 전환

- 아래 header를 추가한다.

#include <linux/gfp.h>

#include <linux/slab.h>

#include <linux/mm.h>

7) 기타 compile을 하면서 자잔한 warning & error를 수정해 나간다.

📌 참고: linux kernel은 C90 compiler를 기본으로 하고 있기 때문에 C99 기반의 코드 사용시 error가 발생하니 주의한다.

8) message.h를 수정하여 kyber public key와 ciphertext를 message에 포함시킨다.

9) noise.[ch] 파일일 수정하여, [그림 5.3]의 내용을 구현한다.

c) 2대의 Nano Pi간 동작 시험

지금까지 작업한 내용을 아래와 같이 NanoPi 2대에 적용하여, Quantum Safe WireGuard가 정상 동작하는지를 확인해 보도록 한다.

$ export ARCH=arm64

$ export CROSS_COMPILE=aarch64-linux-gnu-

$ export PATH=/opt/FriendlyARM/toolchain/11.3-aarch64/bin:$PATH

$ export CC=aarch64-linux-gnu-gcc

$ export LD=aarch64-linux-gnu-ld

$ cd kernel

$ make nanopi4_linux_defconfig

$ make menuconfig

$ make -j8

📌 kernel/drivers/net/wireguard/wireguard.ko 파일을 target board로 복사한다.

[그림 5.4] Nano Pi 2개로 구성된 Quantum Safe WireGuard 테스트베드

<NanoPi 1 설정>

Nano Pi 1의 wireguard 설정 및 ping 시험 결과는 다음과 같다.

📌 wireguard 설정을 하기 위해서는 먼저 wireguard-tools를 설치해야 한다

# opkg update

# opkg install wireguard-tools

[그림 5.5] Nano Pi 1의 wireguard 설정 및 ping 결과

📌 Handshake message format 및 noise protocol만 일부 변경되었기 때문에, 나머지 설정 부분은 기존과 동일하다. 뿐만 아니라 이후 암호화(ChaCha20Poly1305 AEAD) 처리는 기존과 그대로다(즉, 속도 저하가 전혀 없다).

root@FriendlyWrt:~/workspace# lsmod |grep wireguard

wireguard 114688 0

libchacha20poly1305 16384 1 wireguard

libcurve25519_generic 40960 1 wireguard

udp_tunnel 24576 2 l2tp_core,wireguard

ip6_udp_tunnel 16384 2 l2tp_core,wireguard

root@FriendlyWrt:~/workspace# rmmod wireguard

root@FriendlyWrt:~/workspace# insmod /root/workspace/wireguard.ko

[ 6753.266363] wireguard: WireGuard 1.0.0 loaded. See www.wireguard.com for information.

[ 6753.267921] wireguard: PQC(Kyber768 KEM) for WireGuard NoiseIK is ready.

root@FriendlyWrt:~/workspace#

root@FriendlyWrt:~/workspace# lsmod |grep wireguard

wireguard 114688 0

libchacha20poly1305 16384 1 wireguard

libcurve25519_generic 40960 1 wireguard

udp_tunnel 24576 2 l2tp_core,wireguard

ip6_udp_tunnel 16384 2 l2tp_core,wireguard

<NanoPi 2 설정>

한편, Nano Pi 2의 wireguard 설정 및 ping 시험 결과는 다음과 같다.

[그림 5.6] Nano Pi 2의 wireguard 설정 및 ping 결과

OK, 정상적으로 동작한다. Great~ 😎

6. Alpine Linux 용 Quantum Safe WireGuard 구현하기

이번 장에서는 아주 작고(lightweight), 안전한(secure) linux로 알려진 Alpine linux kernel에 Quantum Safe WireGuard를 올리는 과정을 소개해 보고자 한다. 🏂

[그림 6.1] Alpine Linux Logo

a) Alpine Linux 소개
아주 오래 전(Long long ago 호랑이 담배 피던 시절에~ 😓)에 LEAF(Linux Embedded Appliance Framework)라는 project를 이용하여 Linux Router를 개발했던 적이 있다. 최근 들어 LEAF로 network 장비를 만들어 볼까 하는 마음에 다시 찾던 중, LEAF는 없어지고 그 후예(fork)로 Alpine linux가 있다는 사실을 알게 되었다.

b) Alpine Linux kernel build하기
이번 장에서는 Alpine Linux가 이미 설치되어 있는 서버(Intel CPU)상에서 alpine linux kernel을 build하는 절차를 소개하고자 한다.
📌 Alpine linux는 경량한 구조 덕분에 docker에 올라가는 OS로도 널리 알려져 있다. 따라서 아래 제시하는 내용은 Ubuntu PC에 Docker를 설치하고, 다시 docker 내에 Alpine linux를 설치한 후 테스트해 보아도 동일한 결과를 얻을 수 있다. 실제로 필자는 이와 같은 환경에서 개발을 하긴한다. 하지만, kernel build 속도가 아무래도 신경이 쓰이기 때문에 오늘은 실제 server에서 build하는 형태로 접근해 보자.

1) Kernel build 전 준비 작업(주요 패키지 설치)

📌 Alpine linux를 설치하는 내용은 다루지 않는다. 따라서 아래 내용은 이미 Alpine linux가 설치되었다고 가정하고 진행하도록 한다.

$ sudo apk update

$ sudo apk upgrade

$ sudo apk add vim alpine-sdk

/ # visudo /etc/sudoers

...

## User privilege specification

root ALL=(ALL) ALL

chyi ALL=(ALL) ALL //사용하는 계정을 등록한다.

...

$ sudo vi /etc/abuild.conf
PACKAGER 부분을 자신의 정보로 수정한다.

...

PACKAGER="Chunghan.Yi <chunghan.yi@gmail.com>"

MAINTAINER="$PACKAGER"

...

$ sudo addgroup chyi abuild

📌 group 추가 내용이 반영되려면, logout 후 재 login해 주어야 한다.

$ abuild-keygen -a -i

>>> Generating public/private rsa key pair for abuild

Enter file in which to save the key [/home/chyi/.abuild/chunghan.yi@gmail.com-61331fa6.rsa]: <Enter>

Generating RSA private key, 2048 bit long modulus (2 primes)

......+++++

......................................................................+++++

e is 65537 (0x010001)

writing RSA key

>>> Installing /home/chyi/.abuild/chunghan.yi@gmail.com-61331fa6.rsa.pub to /etc/apk/keys...

>>>

>>> Please remember to make a safe backup of your private key:

>>> /home/chyi/.abuild/chunghan.yi@gmail.com-61331fa6.rsa

2) Kernel build 하기 1 - 한번에 build 하기

$ git clone https://github.com/alpinelinux/aports

$ cd aports
$ ls -la
total 344
drwxr-sr-x 12 chyi chyi 4096 Sep 4 07:19 .
drwxr-sr-x 3 chyi chyi 4096 Sep 4 07:16 ..
-rw-r--r-- 1 chyi chyi 1631 Sep 4 07:19 .drone.yml
-rw-r--r-- 1 chyi chyi 371 Sep 4 07:19 .editorconfig
drwxr-sr-x 8 chyi chyi 4096 Sep 4 07:19 .git
drwxr-sr-x 2 chyi chyi 4096 Sep 4 07:19 .githookssudo
drwxr-sr-x 2 chyi chyi 4096 Sep 4 07:19 .github
-rw-r--r-- 1 chyi chyi 105 Sep 4 07:19 .gitignore
drwxr-sr-x 2 chyi chyi 4096 Sep 4 07:19 .gitlab
-rw-r--r-- 1 chyi chyi 2101 Sep 4 07:19 .gitlab-ci.yml
-rw-r--r-- 1 chyi chyi 1115 Sep 4 07:19 .mailmap
-rw-r--r-- 1 chyi chyi 5973 Sep 4 07:19 CODINGSTYLE.md
-rw-r--r-- 1 chyi chyi 5821 Sep 4 07:19 COMMITSTYLE.md
-rw-r--r-- 1 chyi chyi 881 Sep 4 07:19 README.md
drwxr-sr-x 4047 chyi chyi 135168 Sep 4 07:19 community
drwxr-sr-x 1530 chyi chyi 49152 Sep 4 07:19 main
drwxr-sr-x 21 chyi chyi 4096 Sep 4 07:19 non-free
drwxr-sr-x 2 chyi chyi 4096 Sep 4 07:19 scripts
drwxr-sr-x 2318 chyi chyi 69632 Sep 4 07:19 testing
drwxr-sr-x 261 chyi chyi 12288 Sep 4 07:19 unmaintained

$ cd ~/aports/main/linux-lts

$ abuild -r

abuild는 현재 디렉토리에 있는 APKBUILD 파일을 이용하여 build를 진행한다. -r option을 줄 경우, source download & patch 부터 kernel build 후 package 생성까지를 모두 처리한다. Build가 끝난 후에는 build 과정에서 생성한 src/ 디렉토리를 통째로 날려 버린다.

https://wiki.alpinelinux.org/wiki/APKBUILD_Reference

...

>>> linux-lts: Building main/linux-lts 5.10.61-r0 (using abuild 3.8.0_rc4-r0) started Sat, 04 Sep 2021 08:25:02 +0000

>>> linux-lts: Checking sanity of /home/chyi/aports/main/linux-lts/APKBUILD...

>>> linux-lts: Analyzing dependencies...

>>> linux-lts: Installing for build: build-base mkinitfs perl gmp-dev elfutils-dev bash flex bison sed installkernel bc linux-headers linux-firmware-any openssl-dev diffutils findutils

WARNING: Ignoring /home/chyi/packages//main: No such file or directory

(1/128) Installing lddtree (1.26-r2)

(2/128) Installing xz-libs (5.2.5-r0)

(3/128) Installing zstd-libs (1.4.9-r1)

(4/128) Installing kmod (29-r0)

(5/128) Installing libblkid (2.37-r0)

(6/128) Installing argon2-libs (20190702-r1)

(7/128) Installing device-mapper-libs (2.02.187-r1)

(8/128) Installing json-c (0.15-r1)

(9/128) Installing libuuid (2.37-r0)

(10/128) Installing cryptsetup-libs (2.3.6-r0)

(11/128) Installing kmod-libs (29-r0)

(12/128) Installing mkinitfs (3.5.0-r0)

Executing mkinitfs-3.5.0-r0.post-install

(13/128) Installing libbz2 (1.0.8-r1)

(14/128) Installing perl (5.32.1-r0)

(15/128) Installing libgmpxx (6.2.1-r0)

(16/128) Installing gmp-dev (6.2.1-r0)

(17/128) Installing fts (1.2.7-r1)

(18/128) Installing libelf (0.182-r1)

(19/128) Installing xz-dev (5.2.5-r0)

(20/128) Installing zlib-dev (1.2.11-r3)

(21/128) Installing elfutils-dev (0.182-r1)

(22/128) Installing readline (8.1.0-r0)

(23/128) Installing bash (5.1.4-r0)

Executing bash-5.1.4-r0.post-install

(24/128) Installing m4 (1.4.18-r2)

(25/128) Installing flex (2.6.4-r2)

(26/128) Installing bison (3.7.6-r0)

(27/128) Installing sed (4.8-r0)

...

(116/128) Purging kmod-libs (29-r0)

(117/128) Purging xz-libs (5.2.5-r0)

(118/128) Purging zstd-libs (1.4.9-r1)

(119/128) Purging cryptsetup-libs (2.3.6-r0)

(120/128) Purging libblkid (2.37-r0)

(121/128) Purging argon2-libs (20190702-r1)

(122/128) Purging device-mapper-libs (2.02.187-r1)

(123/128) Purging json-c (0.15-r1)

(124/128) Purging libuuid (2.37-r0)

(125/128) Purging libbz2 (1.0.8-r1)

(126/128) Purging fts (1.2.7-r1)

(127/128) Purging zlib-dev (1.2.11-r3)

(128/128) Purging readline (8.1.0-r0)

Executing busybox-1.33.1-r3.trigger

OK: 233 MiB in 58 packages

>>> linux-lts: Updating the main/x86_64 repository index...

>>> linux-lts: Signing the index...

Build 결과는 ~/packages 디렉토리에 자동으로 생성된다.

$ cd ~/packages/

$ ls -la

total 12

drwxr-sr-x 3 pufbox pufbox 4096 Jan 30 20:09 .

drwxr-sr-x 7 pufbox pufbox 4096 Jan 30 20:09 ..

drwxr-sr-x 3 pufbox pufbox 4096 Jan 30 20:09 main

$ cd main/

$ ls -la

total 12

drwxr-sr-x 3 pufbox pufbox 4096 Jan 30 20:09 .

drwxr-sr-x 3 pufbox pufbox 4096 Jan 30 20:09 ..

drwxr-sr-x 2 pufbox pufbox 4096 Jan 30 20:09 x86_64

$ cd x86_64/

$ ls -la

total 93356

drwxr-sr-x 2 pufbox pufbox 4096 Jan 30 20:09 .

drwxr-sr-x 3 pufbox pufbox 4096 Jan 30 20:09 ..

-rw-r--r-- 1 pufbox pufbox 904 Jan 30 20:09 APKINDEX.tar.gz

-rw-r--r-- 1 pufbox pufbox 74925531 Jan 30 20:09 linux-lts-5.15.24-r0.apk

-rw-r--r-- 1 pufbox pufbox 20655011 Jan 30 20:09 linux-lts-dev-5.15.24-r0.apk

📌 최종 build 결과물은 apk(zip 파일) 파일 형태로 생성된다.

3) Kernel build 하기 2 - 단계별 build 하기

APKBUILD를 사용할 경우 맨 마지막에 cleaup( ) 과정을 거치게 되므로, build를 위해 download한 source code가 자동 삭제되는 문제가 있다. 앞으로 WireGuard source code를 자유롭게 compile하려면 kernel source를 삭제해서는 안된다.

📌 아래 내용 중 linux kernel version이 약간씩 다르게(linux-5.10 or linux-5.15) 기술된 부분이 있는데, 이는 정리한 내용의 시간 차에 기인한 것이므로 양해를 바란다.

sanitycheck() -> clean()-> fetch() -> verify() -> unpack() -> prepare() -> mkusers() -> build() -> check() -> package() -> subpackages() -> language packs -> apk -> cleanup()

지금 부터는 이 방법을 소개해 보고자 한다. 먼저 kernel build가 원할히 진행되기 위해서는 몇가지 apk package를 먼저 설치해야 한다.

<package 설치>

$ sudo apk add perl

$ sudo apk add gmp-dev

$ sudo apk add elfutils-dev

$ sudo apk add bash

$ sudo apk add flex

$ sudo apk add bison

$ sudo apk add sed

$ sudo apk add installkernel

$ sudo apk add bc

$ sudo apk add linux-headers

$ sudo apk add linux-firmware-any

$ sudo apk add openssl-dev

$ sudo apk add diffutils

$ sudo apk add findutils

⇒ APKBUILD 내용 참조

⇒ 이 부분을 생략하면 kernel build가 안되니 반드시 설치하도록 한다.

⇒ abuild -r로 full build를 할 경우에는 마지막 단계에서 설치한 package를 uninstall 한다.

아, 그런데 위의 절차가 매우 번거롭다. 이를 한방에 처리할 수는 없을까 ?

$ abuild deps

⇒ 앞서 한 작업을 대신한다. :)

$ abuild fetch

⇒ source code download하여 /var/cache/distfiles 디렉토리에 위치시킨다.

⇒ 물론 이미 받아두었다면, 다시 받지는 않는다.

>>> linux-lts: Fetching https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.10.tar.xz

% Total % Received % Xferd Average Speed Time Time Time Current

Dload Upload Total Spent Left Speed

100 111M 100 111M 0 0 10.9M 0 0:00:10 0:00:10 --:--:-- 11.1M

>>> linux-lts: Fetching https://cdn.kernel.org/pub/linux/kernel/v5.x/patch-5.10.61.xz

% Total % Received % Xferd Average Speed Time Time Time Current

Dload Upload Total Spent Left Speed

100 1904k 100 1904k 0 0 2450k 0 --:--:-- --:--:-- --:--:-- 2448k

$ abuild verify

⇒ patch file과 kernel config file에 대한 checksum을 verification하는 단계

$ abuild unpack

⇒ /var/cache/distfiles/linux-5.10.tar.xz 파일을 src/ 디렉토리 아래에 푼다.

$ abuild prepare

⇒ kernel patch 적용 후, kernel .config 까지 생성

⇒ build-lts.x86_64/.config

c3d01af6643e:~/workspace/aports/main/linux-lts$ ls -l src/build-lts.x86_64/.config

-rw-r--r-- 1 chyi chyi 224952 Sep 15 05:29 src/build-lts.x86_64/.config

$ abuild build

⇒ kernel build

---------<내부 동작>--------------------------------------------------------------------

abuild build를 하면 내부적으로 대략 아래와 같은 일을 수행한다(실제 menuconfig 단계는 수행하지 않음).

$ cd src/linux-5.10

$ make -C ../build-lts.x86_64 menuconfig

[그림 6.2] linux kernel menuconfig

$ make ARCH=x86_64 CC=gcc KBUILD_BUILD_VERSION=1-Alpine -C ../build-lts.x86_64

⇒ kernel image 생성하기

⇒ (아주 오랜 시간 경과 후) ../src/build-lts.x86_64 디렉토리 아래에 vmlinux 파일이 생성된다.

$ make ARCH=x86_64 CC=gcc KBUILD_BUILD_VERSION=1-Alpine -C /home/chyi/workspace/aports/main/linux-lts/src/build-lts.x86_64 modules

⇒ kernel module build 하기

----------------------------------------------------------------------------------------

📌 수동으로 Kernel build하는 방법을 알아둘 필요가 있다. 그래야 새로운 kernel module을 추가하거나, kernel code를 수정할 경우 좀 더 편해질 수 있다.

__________________________________________

<여기서 잠깐>

실제 linux kernel site에서 download한 kernel source code는 어디에 있을까 ? 실제로 우리가 kernel code를 수정한다면 어디에서 하는게 맞을까 ?

$ cd /var/cache/distfiles

$ ls -la

total 115896

drwxrwxr-x 1 root abuild 4096 Sep 15 01:51 .

drwxr-xr-x 1 root root 4096 Sep 6 01:05 ..

-rw-r--r-- 1 chyi chyi 116606704 Sep 6 08:11 linux-5.10.tar.xz

-rw-r--r-- 1 chyi chyi 1950496 Sep 6 08:11 patch-5.10.61.xz

drwxr-xr-x 3 chyi chyi 4096 Sep 9 01:52 src

__________________________________________

$ abuild rootpkg

⇒ Kernel과 kernel module이 포함된 package 생성

$ ls -la pkg/

total 44

drwxr-sr-x 10 chyi chyi 4096 Sep 15 02:46 .

drwxr-sr-x 1 chyi chyi 4096 Sep 15 02:42 ..

drwxr-sr-x 2 chyi chyi 4096 Sep 15 02:48 .control.linux-lts

drwxr-sr-x 2 chyi chyi 4096 Sep 15 02:47 .control.linux-lts-dev

drwxr-sr-x 5 chyi chyi 4096 Sep 15 02:46 linux-lts

drwxr-sr-x 4 chyi chyi 4096 Sep 15 02:43 linux-lts-dev

만일 초기화한 상태에서 처음부터 다시 build를 하고자 한다면, 아래 명령을 수행할 수 있다.

$ abuild clean

⇒ linux-tls/src 디렉토리를 통째로 날린다.

$ abuild cleancache

⇒ /var/cache/disfiles 아래에 download해 두었던 kernel & patch source를 모두 삭제한다.

<참고 사항>

abuild 관련 주요 명령 option을 정리해 보면 다음과 같다.

[그림 6.3] abuild 사용법

📌 abuild 알면 알수록 꽤 괜찮은 tool이다. Yocto project의 bitbake와 유사하다고나 할까 ...

c) WireGuard에 Kyber KEM 추가하기

이번 절에서는 5장에서 작업한 내용을 Alpine linux(정확히는 Intel x86_64 server)에 porting하는 과정을 소개하고자 한다. Intel x86_64에서는 AVX2(Avanced Vector eXtentions) 기능이 있다. 자세한 사항은 [참고문헌 13]을 참조하도록 하자.

AVX programming에 관해서는 아래 site에 쉽게 정리되어 있으니, 참고하기 바란다.

https://yunmorning.tistory.com/31

나머지 부분은 5장의 내용과 동일하다. pass~ 😜

d) Porting 절차 요약

Wireguard에 CRYSTALS Kyber KEM을 적용하기 위해 필요한 porting 절차를 정리해 보기로 한다. Porting을 위해 사용한 code는 역시 PQClean이 되겠다.

https://github.com/PQClean/PQClean/crypto_kem/kyber768/avx2

<porting 절차>

1) Makefile을 수정하여 아래 내용을 추가한다.

ccflags-y += -O3 -fvisibility=hidden -msse2avx -mavx2 -mbmi2 -mpopcnt

ccflags-y += -Wframe-larger-than=3072

wireguard-y += kyber/avx2/cbd.o

wireguard-y += kyber/avx2/consts.o

wireguard-y += kyber/avx2/fips202.o

wireguard-y += kyber/avx2/sha2.o

wireguard-y += kyber/avx2/fips202x4.o

wireguard-y += kyber/avx2/indcpa.o

wireguard-y += kyber/avx2/kem.o

wireguard-y += kyber/avx2/poly.o

wireguard-y += kyber/avx2/polyvec.o

wireguard-y += kyber/avx2/rejsample.o

wireguard-y += kyber/avx2/symmetric-shake.o

wireguard-y += kyber/avx2/verify.o

wireguard-y += kyber/avx2/kex.o

wireguard-y += kyber/avx2/basemul.o

wireguard-y += kyber/avx2/fq.o

wireguard-y += kyber/avx2/invntt.o

wireguard-y += kyber/avx2/ntt.o

wireguard-y += kyber/avx2/shuffle.o

wireguard-y += kyber/avx2/keccak4x/KeccakP-1600-times4-SIMD256.o

2) userspace용 C header를 제거하고, kernel header로 교체한다.

#include <stdint.h> => #include <linux/types.h>

#include <stddef.h>

#include <string.h> => #include <linux/string.h>

//#include <stdint.h> -> #include <linux/types.h>
//#include <stddef.h>

3) fips202.[ch] 파일을 common에서 복사해 온다. malloc/free code를 kmalloc/kfree code로 전환한다. exit 함수를 제거한다.

4) sha2.[ch] 파일을 common에서 복사해 온다.

5) randombytes.h 파일을 common에서 복사해 온다.

6) keccak4x/* 파일을 common에서 복사해 온다.

7) [중요] #include <immintrin.h> 앞 뒤에 define 문을 추가한다.

#define _MM_MALLOC_H_INCLUDED

#include <immintrin.h>

#undef _MM_MALLOC_H_INCLUDED

8) [중요] error: unknown type name 'size_t'

#include <linux/types.h>를 맨 앞 line으로 이동시킨다.

9) restrict 관련 code 제거한다.

10) [중요] local buffer size가 큰 경우, array 관련 코드를 kmalloc 등으로 교체한다. 이 작업을 안할 경우 system이 그냥 뻗어 버린다.

- stack buffer size 2048 이상의 경우 kmalloc으로 교체 검토

- indcpa.c의 keypair, enc, dec 3개 함수 polyvec, poly 부분 kmalloc으로 전환

- 아래 header를 추가한다.

#include <linux/gfp.h>

#include <linux/slab.h>

#include <linux/mm.h>

11) 기타 compile을 하면서 자잔한 warning & error를 수정해 나간다.

📌 참고: linux kernel은 C90 compiler를 기본으로 하고 있기 때문에 C99 기반의 코드 사용시 error가 발생하니 주의한다.

12) message.h를 수정하여 kyber public key와 ciphertext를 message에 포함시킨다.

13) noise.[ch] 파일일 수정하여, [그림 5.3]의 내용을 구현한다.

e) Intel Server와 Nano Pi간 동작 시험

지금까지 작업한 내용을 아래와 같이 Intel Server에 올리고, 5장에서 구현한 NanoPi와 연동시켜, Quantum Safe WireGuard가 정상 동작하는지를 확인해 보도록 한다.

[그림 6.4] Intel Server

<Alpine linux가 탑재된 Intel Server>

$ cat start_wg.sh

#!/bin/sh
#wg genkey | tee ./privatekey | wg pubkey > ./publickey
sudo rmmod wireguard
sudo insmod avx2/wireguard.ko
sudo ip link add dev wg0 type wireguard
sudo ip address add dev wg0 10.1.1.5/24
sudo ip link set up dev wg0
sudo wg set wg0 listen-port 51820 private-key ./privatekey peer 9MXZLGChppVQ3oEcuQHz+axs6sU4sE9FJCn27jGqVQk= allowed-ips 10.1.1.0/24 endpoint 192.168.1.79:51820

$ sudo wg show

interface: wg0

public key: l5C3jiGLBXoMUAVaAU+BbQaukRWJamlHfkBfsADcqhY=

private key: (hidden)

listening port: 51820

peer: 9MXZLGChppVQ3oEcuQHz+axs6sU4sE9FJCn27jGqVQk=

endpoint: 192.168.1.79:51820

allowed ips: 10.1.1.0/24

$ ping 10.1.1.200

PING 10.1.1.200 (10.1.1.200): 56 data bytes

64 bytes from 10.1.1.200: seq=0 ttl=42 time=3968.722 ms

64 bytes from 10.1.1.200: seq=4 ttl=42 time=2.387 ms

64 bytes from 10.1.1.200: seq=5 ttl=42 time=2.652 ms

64 bytes from 10.1.1.200: seq=6 ttl=42 time=2.290 ms

OK, nano pi 1(10.1.1.200)으로 정상 ping이 된다. Great~ 😎

이상으로 CRYSTALS Kyber 알고리즘을 WireGuard Protocol과 접목하고, 이를 NanoPi R4S 보드와 Intel Server(Alpine linux 탑재)에서 동작시켜 보았다. 끝까지 읽어 주셔서 감사 드리며, 부족한 부분은 (언제나 그렇듯) 다음을 기약해 본다. "May the Source be with You" 😋

<TODO>

1) WireGuard Windows Client에 CRYSTALS Kyber KEM 적용하기

2) WireGuard Android App에 CRYSTALS Kyber KEM 적용하기

3) WireGuard MacOS Client에 CRYSTALS Kyber KEM 적용하기

4) AVX2 Kyber code를 AVX512로 변경하기

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

7. References
[1] https://wiki.friendlyelec.com/wiki/index.php/NanoPi_R4S#Install_OS

[2] https://namu.wiki/w/ARM%20big.LITTLE%20%EC%86%94%EB%A3%A8%EC%85%98

[3] https://www.ubergizmo.com/2013/01/what-is-arm-big-little/

[4] https://www.wireguard.com/

[5] Post-quantum WireGuard, Andreas Hülsing, Kai-Chun Ning, Peter Schwabe, Florian Weber, Philip R. Zimmermann

[6] https://sar.informatik.hu-berlin.de/research/publications/SAR-PR-2020-03/SAR-PR-2020-03_.pdf