第一届OpenHarmonyCTF

发表于 分类于 阅读次数： Waline： 本文字数： 1.3k 阅读时长 ≈ 5 分钟

第一届OpenHarmony CTF专题赛 Crypto题解

赛题不是很难， 但是套了层鸿蒙，还挺有意思的。

Weak_random

seed的范围很小，可以直接爆，iv不影响CBC第一块密文之后的解密结果，所以不用管iv

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from Crypto.Cipher import AES
from tqdm import trange
import random
import os
import hashlib

enc = "a4d1a3d4a4c5eee0834449f1ed4539b3b29157825d0dbfa51e84525bb00ed5b5f462e994a2c742baa5fb90977507983c"
check = "063043351f9576f5ffeaa565da8edf70dad688fd8b406742fa166de432d1ae27"

for entropy_part1 in trange(10000):
    for entropy_part2 in range(256):
        final_seed = entropy_part1 + (entropy_part2 << 8) 
        random.seed(final_seed)
        key = random.getrandbits(128)
        iv = os.urandom(16)
        keybyte = long_to_bytes(key)
        if len(keybyte) == 16:
            aes = AES.new(keybyte,AES.MODE_CBC,iv)
            flag = aes.decrypt(bytes.fromhex(enc))[-32:]
            if hashlib.sha256(flag).hexdigest() == check:
                print(flag)
                break
                # flag{0428f4ff1a4e3d2e2326552f9db48fa9}

Ea5y_RSA

两个关键文件是，entry/src/main/ets/util路径下的RsaUtil.ets和entry/src/main/ets/page下的Index.ets

RsaUtil.ets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import { cryptoFramework } from '@kit.CryptoArchitectureKit';
import { buffer } from '@kit.ArkTS';

class RsaUtil{
  private keyPair: cryptoFramework.KeyPair | null = null;

  constructor() {
    let keyGenerator = cryptoFramework.createAsyKeyGenerator('RSA1024');
    this.keyPair = keyGenerator.generateKeyPairSync();
  }
  encrypt(data: string): cryptoFramework.DataBlob{
    let plainText: cryptoFramework.DataBlob = { data: new Uint8Array(buffer.from(data, 'utf-8').buffer) };

    if(this.keyPair != null){
      return this.rsaEncryptBySegment(this.keyPair.pubKey, plainText);
    }else{
      console.error('Key is null');
      return plainText;
    }
  }
  rsaEncryptBySegment(pubKey: cryptoFramework.PubKey, plainText: cryptoFramework.DataBlob) {
    let cipher = cryptoFramework.createCipher('RSA1024|PKCS1');
    cipher.initSync(cryptoFramework.CryptoMode.ENCRYPT_MODE, pubKey, null);
    let plainTextSplitLen = 64;
    let cipherText = new Uint8Array();
    for (let i = 0; i < plainText.data.length; i += plainTextSplitLen ) {
      let updateMessage = plainText.data.subarray(i, i + plainTextSplitLen );
      let updateMessageBlob: cryptoFramework.DataBlob = { data: updateMessage };
      let updateOutput = cipher.doFinalSync(updateMessageBlob);
      let mergeText = new Uint8Array(cipherText.length + updateOutput.data.length);
      mergeText.set(cipherText);
      mergeText.set(updateOutput.data, cipherText.length);
      cipherText = mergeText;
    }
    let cipherBlob: cryptoFramework.DataBlob = { data: cipherText };
    return cipherBlob;
  }
  getGift(): number[]{
    let gift: number[] = [0];
    if(this.keyPair != null){
      let pri = this.keyPair.priKey.getEncoded().data;

      for(let i: number = 7; i < 285; i++){
        gift.push(pri[i]);
      }
    }
    return gift;
  }
}

export default new RsaUtil();

Index.ets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
check(){
  let encryptText = RsaUtil.encrypt(this.flag);
  let base64 = new util.Base64Helper();
  let c = base64.encodeToStringSync(encryptText.data);

  if(c === '2z/TenC2n+eLR6WbO8mQcJsdKMasdA2/K6xDQj2ABqZvMz1PHTdUvnw7YcFv9fM7BYqf7WCbVFYzJINUeseI7f+72PEw6XuTyDW4s6nE6bZr51XrX383raumpOxUwryCudjsFEsDRmq16sgf0Rk2KJCVLyaXhDstMux+VumSaEY='){
    promptAction.showToast({
      message: "Wow, you find the true flag"
    })
  }else{
    promptAction.showToast({
      message: "oh, Sorry. But In my Log, this is a gift for you"
    })
    let gift = RsaUtil.getGift();
    console.log('my gift:', gift);
  }
}

从RsaUtil.ets中的rsaEncryptBySegment函数可以知道，hint是RSA私钥文件的第7-284字节，恢复一下

1
2
3
4
5
6
hint = [48,13,6,9,42,134,72,134,247,13,1,1,1,5,0,4,130,2,97,48,130,2,93,2,1,0,2,129,129,0,219,91,76,137,49,174,41,189,193,240,64,187,23,143,171,74,107,120,166,142,186,244,90,56,6,54,147,63,158,119,222,110,46,245,223,167,190,173,76,7,36,210,188,249,83,151,200,24,88,11,247,108,112,208,109,173,32,143,133,158,62,83,232,150,60,120,232,201,90,239,207,77,200,36,2,107,62,204,214,35,28,190,48,150,242,52,247,4,11,255,164,13,122,170,42,223,66,36,114,134,183,30,99,21,31,224,194,169,223,86,12,216,139,0,255,220,115,223,83,90,71,25,221,180,160,8,212,41,2,3,1,0,1,2,129,128,82,97,158,131,227,241,153,225,151,69,136,185,251,38,76,217,93,53,105,176,47,12,120,25,148,83,200,199,90,215,127,228,247,164,5,196,52,251,86,147,84,68,5,14,202,83,53,165,214,227,95,160,13,90,105,230,92,85,42,132,124,185,252,158,69,85,122,160,246,99,167,168,183,89,173,57,73,126,186,253,22,111,92,152,14,5,95,175,46,189,186,93,207,30,207,8,231,173,143,91,128,18,58,6,25,209,64,207,123,224,255,177]
plaintext = ''
for i in hint:
    plaintext += hex(i)[2:].zfill(2)
    
print(plaintext)

得到

1
300d06092a864886f70d0101010500048202613082025d02010002818100db5b4c8931ae29bdc1f040bb178fab4a6b78a68ebaf45a380636933f9e77de6e2ef5dfa7bead4c0724d2bcf95397c818580bf76c70d06dad208f859e3e53e8963c78e8c95aefcf4dc824026b3eccd6231cbe3096f234f7040bffa40d7aaa2adf42247286b71e63151fe0c2a9df560cd88b00ffdc73df535a4719ddb4a008d429020301000102818052619e83e3f199e1974588b9fb264cd95d3569b02f0c78199453c8c75ad77fe4f7a405c434fb56935444050eca5335a5d6e35fa00d5a69e65c552a847cb9fc9e45557aa0f663a7a8b759ad39497ebafd166f5c980e055faf2ebdba5dcf1ecf08e7ad8f5b80123a0619d140cf7be0ffb1

按pem文件格式稍微区分一下

1
2
3
4
5
6
7
300d06092a864886f70d0101010500048202613082025d
020100
	02818100
db5b4c8931ae29bdc1f040bb178fab4a6b78a68ebaf45a380636933f9e77de6e2ef5dfa7bead4c0724d2bcf95397c818580bf76c70d06dad208f859e3e53e8963c78e8c95aefcf4dc824026b3eccd6231cbe3096f234f7040bffa40d7aaa2adf42247286b71e63151fe0c2a9df560cd88b00ffdc73df535a4719ddb4a008d429
	0203
		010001
	028180	52619e83e3f199e1974588b9fb264cd95d3569b02f0c78199453c8c75ad77fe4f7a405c434fb56935444050eca5335a5d6e35fa00d5a69e65c552a847cb9fc9e45557aa0f663a7a8b759ad39497ebafd166f5c980e055faf2ebdba5dcf1ecf08e7ad8f5b80123a0619d140cf7be0ffb1

从中提取出n，e，以及d的高位（895bit），那大概率是低位128未知。

我的思路是用
$$
k’ = \frac{e\times d_h}{n} + 1
$$
来近似正确的k，实际上这就是正确的k

然后令
$$
S = N + 1 - \frac{(e\times d_h)}{k}
$$

$$
D = \sqrt{S^2 - 4n}
$$

然后计算
$$
p_h = \frac{S + D}{2}
$$
得到的$p_h$和正确的$p$差了低128bit左右，一元copper得解

思路来源：Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import *
import base64
import gmpy2

n = 0xdb5b4c8931ae29bdc1f040bb178fab4a6b78a68ebaf45a380636933f9e77de6e2ef5dfa7bead4c0724d2bcf95397c818580bf76c70d06dad208f859e3e53e8963c78e8c95aefcf4dc824026b3eccd6231cbe3096f234f7040bffa40d7aaa2adf42247286b71e63151fe0c2a9df560cd88b00ffdc73df535a4719ddb4a008d429
e = 0x10001
dh = 0x52619e83e3f199e1974588b9fb264cd95d3569b02f0c78199453c8c75ad77fe4f7a405c434fb56935444050eca5335a5d6e35fa00d5a69e65c552a847cb9fc9e45557aa0f663a7a8b759ad39497ebafd166f5c980e055faf2ebdba5dcf1ecf08e7ad8f5b80123a0619d140cf7be0ffb1
c = "2z/TenC2n+eLR6WbO8mQcJsdKMasdA2/K6xDQj2ABqZvMz1PHTdUvnw7YcFv9fM7BYqf7WCbVFYzJINUeseI7f+72PEw6XuTyDW4s6nE6bZr51XrX383raumpOxUwryCudjsFEsDRmq16sgf0Rk2KJCVLyaXhDstMux+VumSaEY="
c = bytes_to_long(base64.b64decode(c))
unknown = 128
dh = dh << unknown
k = e * dh // n + 1

# 求p的高位
S = n + 1 - ((e*dh - 1) // k)
D = gmpy2.iroot(abs(S**2 - 4*n),2)[0]
tmp = int((S + D) // 2)
ph = tmp >> 140 << 140
# 恢复p
R.<x> = PolynomialRing(Zmod(n))
f = ph + x
res = f.small_roots(X=2^140,beta=0.49)
p = int(ph + res[0])
q = n // p
d = inverse(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
# flag{O1d_WIN3_In_4_New_B0ttlE_HAhAh4HAHA}

Small Message For (SM4) Encryption

猜测secret_message很短，直接爆破

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from gmssl import sm4
from itertools import product

leak = bytes.fromhex("ee278c4e526ff15b8d308b6b18f83221")
ciphertext = bytes.fromhex("d9ea43b0d208aa168e4a275a69df3bc86051e756f9ca7959b68c6b23c9e1b69c19e08b75938375a6be830d1844d8a6e368faf1ddffecea69b5abe00ac0d6e10d6696be33d40e83a272072fbe131f98c82587011f61f2d58a020c8c54cf9b651abd740a3d55d36daa9c88cfc10a520ce4211fba4365ce98b82355b17c64dd2de4800fc68df36cfa8a3fd05baac6970dcd")

def decrypt(ciphertext, key, iv):
    cipher = sm4.CryptSM4(sm4.SM4_DECRYPT)
    cipher.set_key(key, sm4.SM4_DECRYPT)
    return cipher.crypt_cbc(iv, ciphertext)

def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))

printable = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_{}"

for length in range(1,17):
    print(f"正在尝试长度为:{length}")
    for i in product(printable, repeat=length):
        secret_message = bytes(i)
        key = secret_message
        while len(key) < 16:
            key += secret_message
        iv = xor(key, leak)
        plaintext = decrypt(ciphertext, key, iv)
        if b'flag' in plaintext:
            print(f"key = {key}")
            print(plaintext)

得到

1
2
key = b'sMsMsMsMsMsMsMsM'
b"My FLAG? If you want it, I'll let you have it... search for it! I left all of it at that place: flag{tHe_m3s5ag3_1s_2_sMa11!11!}"

Simple LLL

定位到关键函数runMixer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public Object #~@0>#runMixer(Object functionObject, Object newTarget, Index this) {
        obj = this.flag;
        if ((this.flag.length < 6 ? 1 : 0) != 0) {
            this.output = "Flag too short!";
            return null;
        }
        if (istrue(("flag{" != obj.substring(0, 5) ? 1 : 0)) != null || isfalse(("}" != obj[obj.length - 1] ? 1 : 0)) == null) {
            this.output = "Invalid flag, must starts with `flag{` and ends with `}`";
            return null;
        }
        substring = obj.substring(5, obj.length - 1);
        if ((0 != (substring.length % 3) ? 1 : 0) != 0) {
            this.output = "Invalid key length (must be multiple of 3)";
            return null;
        }
        i = 0;
        getPrime = this.getPrime(215);
        getPrime2 = this.getPrime(128);
        getPrime3 = this.getPrime(170);
        r36 = [Object];
        obj2 = getiterator("Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof.".substring(0, 50));
        obj3 = obj2.next;
        i2 = 0;
        while (true) {
            callthisN = obj3();
            throw.ifnotobject(callthisN);
            if (istrue(callthisN.done) != null) {
                break;
            }
            r362 = callthisN.value;
            try {
                bytesToLong = this.bytesToLong(substring[i] + substring[i + 1] + substring[i + 2]);
                i += 3;
                r362 = (i >= substring.length ? 1 : 0);
                if (r362 != 0) {
                    i = 0;
                }
                r36.push((this.getRandomBits(190) * getPrime) + ((this.modPow(getPrime2, bytesToLong, getPrime3) * BigInt(r362.charCodeAt(0))) % getPrime3));
            } catch (ExceptionI0 unused) {
                z = r362;
                if (istrue(i2) == null) {
                    i2 = 1;
                    obj4 = null;
                    r363 = hole;
                    try {
                        obj5 = obj2.return;
                        obj3 = obj5;
                        r363 = (0 == obj5 ? 1 : 0);
                    } catch (ExceptionI0 unused2) {
                    }
                    if (r363 == 0) {
                        obj4 = obj3();
                        throw(z);
                        throw.ifnotobject(obj4);
                    }
                }
                throw(z);
            }
        }
        this.output = "P: " + getPrime3 + ", G: " + getPrime2 + "\nEncrypted: [" + r36.join(", ") + "]";
        console.error("P: " + getPrime3 + "");
        console.error("G: " + getPrime2 + "");

先把flag按3字节拆分，然后生成3个素数，加密逻辑是encrypted_i = k_i * getPrime + (getPrime2 ^ flag_i,getPrime3) * ord(s_i) % P，s是上面那串很长的字符串

把后面模P部分看作y_i，就是ACD。拿正交格打出后面DLP部分，然后解DLP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import *
import itertools

P = 1254116318848000721162616841861668357042678028242871
G = 209950396597656524832933655724759236601
Encrypted = [49075650530646745101583770544994878354350706600794137221493223425586773770444878005832637252613273185571525401857599466024, 32462058523831346965301451867146918419501780168654009007894837156535508614721716192457580504544083283156909800751366422095, 30972208810535296088928411886973751419617618309332429902969141779778292135413139940847060084830481982818980039701908647188, 36223574592391465479610118714694121780652259811896545667946982891979827110400079684720554665327962837948029887902911934412, 51083493449145987338071924797694856705969670516974983529541234868336268181840557466743268534891548519807169187995970255210, 46886310857573570123362938810630869611862461311551079654729345179011458677502368863164644598223367343833695547090533503341, 41708987706001718769608385110174384681410129197881430477256694463144195570856661595611916434585980611056756461291298472053, 30432351497415348382971171275378355359918508620694918719611498083801325935877535604696864046477138836882529337593346354232, 37560091205301885324103234765518311779406333692270015257703458177088739786303881151059582186911290629475272554877805151653, 31738173296730605298164313891136444126736390111525241834683826120523560694916544054475801123227319258203564087555114509638, 50467796950716988044567626656972211530828588399176491422572772105434068772625329068013940121046216843532049180580147283042, 32336092218697303538039888038013301651734768870962551231671340266349215882532885410190230501882822408733225249079178061292, 49233450637503908199331577713636388807738552874189785067376543229399582025835470237637909525452461674632729257338416707780, 28924861393443192065262429103620760999268015168472730662823316530606489620828661715860808895274847890501584963069001731650, 29876871203434245756788637186918045878619730844744607066691873635805407116210513937482891978090244921700528166986169373004, 51045530530049998485303784443472394679340537711157110553830035081831280045359882051584398935926529291755099240406457873783, 34236922717566363192133863703148263941004712495034897774573119383475003417834951108666287711404001939048464437002433679407, 45872505907809637020370422271978939675346851543054028587891901912384052395705538771247266287193763510286880060531292639959, 45848898109057344134202435270619102891933756903137918210539806927748378219250477795575772238242834622990352860755134741466, 30690831192388284613442756217051361418365633435900191091970709571717316387519397173976205018862717979518148324020005010923, 31449987807594348386701815071912866455543777241540033790783566519826585105648502178453059357873663927865204928554663236077, 44164522031334631634742032676966915810386287680887515409727547743275857694255961288064333775997899156198169728004798627301, 45435754201870632997035120062097881840301496409175334584690761854547511860361137446247046697532853292820408620710624307382, 44339690473566894343952978154628696880034014523559143611036136185280642456704915048553091007234249154226918623377375894691, 45467002847831254808014906287799768055175059091786525970897932893891805445410961529449204154370320748667361921821962109675, 36672712060609316132155228755904497745191559722524497137141776547016866438152541916275707247661474924785433334031743867273, 33318272036111737761729665211639916834294015786168547961487773974212416192990634928540026070104913562774692957549715549488, 26488446249432698184964155673759155536134402144071339774049243916957631410861616681071512410907603593351545902355432029458, 40341075900310292662475114169415116089541198150649315469712291419180113007460321212589560058895403777206252321908544442309, 26829451620598286750871854925026378833727062253205541621457386970491913105057509287213115121008833266049546890167479802632, 45513592341672142381403583527547085383860968838283026398569419392666884390543295759414462710314345917114880365977486134681, 30989656373000940717564315962045358441783763445149927644939982470127544608520133355349744790032263796611938858721618488033, 44334471499924741874147933306576276027827636768071583554224521981965987566098166455226169818663501835712110724415781328492, 31837426402896485653611477218311016784291450679331542452646112026594865452425670444622297055248688317693429007530695867601, 45542312691317689697293085601643785865987056411657443496979205966506140025833642545782321283634423578256217775226695304197, 30485271545188004895221095186333612748347363012347281545184750365885020656281644717572961657232707805466675963034006872784, 28909547798415865495384409998912720428801877178846539449144055022985800057587307639611234111333806969344999647025832449329, 36474516684693555253555620995281452623013317806760643054084307027361066299499728227911984729226225415113048230141419462563, 39314372710645902875277660511577509635271209111954999042581312773469634841357053636979220063564692737995811930064432927127, 44035251040377727725066806537218009403249809071419110041762050287261847325282865785027211482623438334346368614213368626255, 42188806896882930759219928360233240470234630013801107325372593842833925956327138084141056173119195258281285726246685847703, 49468951309617822848188776411074794337979193322455086362250368127634170021279451014724294108762327145601715669487069984722, 27848903821180797829554971104131819473313526358565662810201287260276042904982964015770224545162808975296175663605065805771, 31042392763667641699655908674042641249895844697990237386851044670925381792328355872131399527030058491850262643670126569454, 48573860100704044325616555512704392764962824964488286580053670612772243734308406893308936032754072647800515547910407250580, 42148920504930890050104940689383752399382140669899852679711608113701470501220517756835304057620414238155337848626148565134, 30537478091813698779272725543057552156908006401377428551485334818175823492053620624881741713726950644848546932655347996830, 41867226276134021326180924978032826959738927139822089673876558682452698080178587784785451606248821128839542546759193575454, 44448580251300888167824584862932031104845007996804107175030122343359380672927551324642723494840716530579291045310013545511, 26835868289472666680392568389484683867336038760181238473634160506663243002110413982694314116878396340095716172647058698157]
msg = "Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof."
s = msg[:50]

n = len(Encrypted)
L = Matrix(ZZ,n,n+1)
for i in range(n):
    L[i,0] = Encrypted[i]
    L[i,i+1] = 1
L[:,0] *= getPrime(1024)

u_matrix = Matrix(ZZ,L.LLL()[:-2,1:])
u_right_kernel = u_matrix.right_kernel().matrix()
for line in u_right_kernel.LLL():
    res = line.list()
    Y = [abs(res[i]) * inverse(ord(s[i]),P) % P for i in range(n)]
    flag = b''
    for _ in range(n):
        for i in itertools.product('0123456789abcdef',repeat=3):
            m = ''.join(i).encode()
            if pow(G,bytes_to_long(m),P) == Y[_]:
                flag += m
    print(flag)

得到

1
f8abee3f93898fdbe1168d414e4f0e3614bfdd629b0f1f8abee3f93898fdbe1168d414e4f0e3614bfdd629b0f1f8abee3f93898fdbe1168d414e4f0e3614bfdd629b0f1f8abee3f93898fd

有重复部分

flag{f8abee3f93898fdbe1168d414e4f0e3614bfdd629b0f1}

-------------已经到底啦！-------------