[CryptoHack] MISC(Armory)

Armory

문제(및 설명)

Shamir의 스키마를 개선하여 결정론적으로 파생된 공유를 사용했습니다. 비트코인 개인 키 및 기타 비밀 데이터 저장에 좋습니다. 당신은 첫 번째 공유만 가지고 있고 플래그를 해제하기 위해 3개가 필요하기 때문에 어떤 가능성도 없습니다.

풀이

#!/usr/bin/env python3

import hashlib

FLAG = b"crypto{???????????????????????}"
PRIME = 77793805322526801978326005188088213205424384389488111175220421173086192558047


def _eval_at(poly, x, prime):
    accum = 0
    for coeff in reversed(poly):
        accum *= x
        accum += coeff
        accum %= prime
    return accum


def make_deterministic_shares(minimum, shares, secret, prime):
    if minimum > shares:
        raise ValueError("Pool secret would be irrecoverable.")

    coefs = [secret]
    for i in range(1, shares + 1):
        coef = hashlib.sha256(coefs[i-1]).digest()
        coefs.append(coef)
    coefs = [int.from_bytes(p, 'big') for p in coefs]
    poly = coefs[:minimum]

    points = []
    for i in range(1, shares + 1):
        point = _eval_at(poly, coefs[i], prime)
        points.append((coefs[i], point))

    return points


shares = make_deterministic_shares(minimum=3, shares=7, secret=FLAG, prime=PRIME)
for share in shares:
    print(share)

(armory.py)

(105622578433921694608307153620094961853014843078655463551374559727541051964080, 25953768581962402292961757951905849014581503184926092726593265745485300657424)

(share.txt)

 

이 문제는 Shamir의 비밀 공유 스키마에 관한 문제입니다.
https://www.theteams.kr/teams/7235/post/70411

해당 문제의 자세한 부분은 이링크에서 참고 했습니다.
차수 t - 1의 다항식은 t개의 점이 알려진 경우에만 알 수 있습니다.

이 문제에서 첫 번째 잠만 알려져 있으므로 값을 알수 없지만,
다른 점을 유추할 수 있습니다:

계수 c는 이전 계수 c1-1의 SHA-256 해시를 계산하여 생성됩니다. 
따라서 c1이 알려진 경우, 계수 C2, C3 등을 생성할 수 있습니다.

생성된 점의 좌표는 계수 자체입니다. 사용된 다항식을 ƒ로 표시하면, 공유에서의 점은 f(c1), f(c2) 등입니다.
 
따라서 다항식의 형식은 c2 * x2 + c1 * x + s입니다. 
s를 플래그 값이라고 생각하면, 플래그 값인 s는 s = y − c2 * c2 + C1 * C1로 유추할 수 있습니다.

import hashlib

p = 77793805322526801978326005188088213205424384389488111175220421173086192558047
FLAG = b"crypto{???????????????????????}"

c1, y = (105622578433921694608307153620094961853014843078655463551374559727541051964080, 25953768581962402292961757951905849014581503184926092726593265745485300657424)
c2 = hashlib.sha256(int.to_bytes(c1, 32, 'big')).digest()
c2 = int.from_bytes(c2, 'big')


pol = (c2 * pow(c1, 2, p) + c1 * c1) % p
print(int.to_bytes((y - pol) % p, len(FLAG), 'big'))

 

플래그값은 crypto{fr46m3n73d_b4ckup_vuln?}입니다.