https://infossm.github.io/blog/2023/12/25/HyperNova/

 

Folding Part 2: HyperNova

이 글에서는 ZKP에서 사용되는 테크닉인 folding의 두 대표적인 논문인 ProtoStar와 HyperNova 중 HyperNova에 대해서 다룬다. https://eprint.iacr.org/2023/573.pdf Preliminaries Incremental Verifiable Computation Incrementally Veri

infossm.github.io

 

2023년은 복잡한 한 해였습니다. 역대 최고로 힘든 한 해에서 많은 것을 잃었지만 동시에 많은 것을 얻은 한 해인 것 같습니다. 

 

매우 간략한 요약을 하자면, 처음으로 매니저 역할을 담당하게 됨과 동시에 ZKP 보안에서 업무를 본격적으로 시작하게 되어 "인간"문제를 다룸에도, "기술"문제를 다룸에도 굉장히 난이도가 높은 문제를 마주치게 되었습니다. 두 개중 하나만 해도 어려울 것 같은데, 둘 다 하려니까 굉장히 난이도가 있었습니다. 아무래도 후자에 조금 더 신경을 많이 쓰고 싶은 개인적 욕심이 있다보니, 전자에 신경을 제대로 쓰지 못해 미안하고 스스로에게 아쉽습니다. 동시에 전자에 신경을 쓰다보니까 ZKP 관련 공부나 제 기술적인 성장에 신경을 쓰기 어려웠고, 그 부분도 아쉽습니다. 뒤에 나오겠지만 2024년부터는 매니저를 접게 되고, 병역을 잘 마치는 것과 제 공부에 집중할 생각입니다. 12월 막판까지도 매니징 관련 문제들로 머리가 많이 아팠는데, 내년에는 조금 더 편안하게 공부에 집중하고자 합니다.

 

ZKP 및 암호/보안

2023년에 꽤 커리어도 실력도 좋아졌습니다. 조금 더 실력이 좋아졌으면 좋겠지만 내년에 더 잘 해봐야겠죠.

 

1월부터 ZK-SCHOOL이라는 ZKP 이론 관련된 프로그램에서 강사로 참가했습니다. 강사진 구성은 Radius 멤버들 + ETH Foundation 멤버들 + 저. 

 

그러다가 본격적인 실마리는 2월에 Jazzy가 한국에 왔을 때, 같이 zkEVM Audit 관련된 논의를 하면서 풀리기 시작했습니다. 

제가 Zellic과 같이 협업해서 zkEVM Audit을 할 수 있는 가능성이 열려서, 이를 실현시키기 위해 노력했습니다. 사실 PBCTF 출제도 이것때문... 

 

https://rkm0959.tistory.com/285

 

A Hyperelliptic Curve Story

A very long story. It started when Brian Gu told me about DARK back in 2021 @theoremoon wrote the challenge "Hell" for SECCON CTF Finals 2022. It involved some hyperelliptic curves and was quite interesting. Let's look at that challenge first. 1 2 3 4 5 6

rkm0959.tistory.com

 

아무튼 그렇게 해서 4월에 실제로 Scroll zkEVM을 Audit 하게 되었습니다! 매우 중요한 프로젝트를 꽤 오랜 기간 붙잡았고, 꽤 많은 버그를 찾아서 기쁩니다. 

이를 위해서 사람들도 만날 겸 몬테네그로로 가서 zuzalu zk week에 참가하기도 했습니다. 지금 돌아보면 조금 더 외향적이었으면 좋았을텐데 싶습니다. 

 

Audit Report는 아래 두 링크에서 공개되어 있습니다. sampriti와 함께 작업했는데, 재밌었습니다. CTF 인맥이 이렇게 이어지네요. 

 

https://github.com/Zellic/publications/blob/master/Scroll%20zkEVM%20-%20Part%201%20-%20Audit%20Report.pdf

https://github.com/Zellic/publications/blob/master/Scroll%20zkEVM%20-%20Part%202%20-%20Audit%20Report.pdf

 

동시에 3월 즈음부터 Axiom Open Source Program에 참가해서 AES와 Poseidon2를 구현했습니다. 그 결과는 아래에.

 

https://rkm0959.tistory.com/290

 

[Axiom OS Project] Implementing Poseidon2 & AES-ECB for Verifiable Encryption

Introduction I participated in the first cohort of the Axiom Open Source Program. After studying and being fascintated with the theory of ZK-friendly hashes, I decided that I will implement some of them for this program. My target for implementation was th

rkm0959.tistory.com

 

이때 Poseidon2의 reference implementation에서 버그를 찾아서 수정을 이끌어냈습니다. Axiom도 결국 여러 방면으로 인연을 이어가게 된 팀입니다. 

 

그러다가 6월에 ETH Seoul에서 발표할 기회가 회사 비즈팀 덕분에 생겨서 발표를 잘하고 왔습니다. 

 

https://www.youtube.com/watch?v=5JFL08oSm4I&t=3200s

 

나중에 이걸 SpearbitDAO에 들고 갔더니 거기에서도 발표를 해달라고 부탁을 받아서 또 발표할 수 있었습니다. 

 

https://www.youtube.com/watch?v=8wsR7o0rOxU 

 

영어 스피킹 능력이 조금 망한 것 같아서 걱정입니다. 사실 SpearbitDAO 발표는 알코올 도핑이 살짝 되어있기는 했습니다 ㅎ_ㅎ;;

 

그러다가 8월 말에 SBC 컨퍼런스 보러 스탠포드 가고 9월 말에 zkSummit10 참석하러 런던가고 끝입니다. 아쉽게도 보안감사 관련 이야기를 다 풀 수는 없어서 내용이 짧네요. 내년에는 더 공개할 수 있으면 좋겠습니다! 고객사 총 3곳을 보안감사했고, 버그도 꽤 찾아서 기뻐요. 내년에도 계속 이 일 할 수 있으면 합니다. 

 

CTF 이야기를 조금 하자면, 출제의 경우 PBCTF에 한 문제, CCE에 한 문제, CODEGATE에 한 문제, WACON에 한 문제 출제했습니다. 

이 중에서 꽤 잘 냈다고 생각하는 문제는 PBCTF의 문제와 CODEGATE에 출제한 문제입니다. PBCTF는 위에 있고, CODEGATE는 https://rkm0959.tistory.com/293

 

CODEGATE 2023 Finals - The Leakers (1 solve)

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 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 8

rkm0959.tistory.com

 

CTF 참가의 경우, 가장 기쁜 것은 ACSC 통과 및 ICC 참가, 그리고 Paradigm CTF 2023 2등을 기록한 것 같습니다. 

뒤에서도 이야기하겠지만 5월에 도쿄에서 만난 minaminao와의 인연이 이어져서 Paradigm CTF 성과에 크게 작용했는데, 신기합니다.

 

순수하게 공부에 대한 이야기를 하자면, 솔직히 그렇게 많이 하지는 못한 것 같습니다. 암호 그 자체에 대한 근본은 생각보다 많이 못 쌓았습니다. 

ZKP 관련해서 모두가 이야기하는 것 관련해서 따라가기 바빴던 한 해 같습니다. 멘탈 관리도 문제고 공부하는 방식에도 약간 문제가 있지 않았나 싶어요.

  • Multivariate Polynomial과 그 Commitment에 대한 조금 더 깊이있는 이해 
  • Spartan 및 Offline Memory Checking 기반의 알고리즘들 
  • Folding에 대한 어느 정도 정확한 이해 
  • 최근에 발전하게 된 다양한 Lookup들에 대한 이해 
  • FRI에 대한 어느 정도 정확한 이해

 

첫 매니저 역할 및 인간적인 이야기

자세한 이야기는 할 수 없지만, 초짜가 다루기에는 엄청나게 민감한 사항들을 다뤄야 했습니다. 저로 인해 상처받은 분들에게 다시 한 번 죄송합니다. 

 

느꼈던 것들을 정리해보자면 

  • 일단 스트레스 관리는 무조건 건강한 방식을 찾아야 합니다. 잘 해소하는 방법을 찾는 게 중요한 것 같아요. 
  • [aggressive 함이 드러나는데 이유도 안 알려줌] < [aggressive 함이 드러나지만 이유는 알려줌] < [aggressive 하지도 않으면서 문제 상황의 이유를 알려줌] 이라고 생각해보면, 결국 화가 나는 이유와 문제 상황에 대해서는 말을 해야합니다. 숨겨진 선택지인 [aggressive 하지 않고 이유도 안 알려줌]은 그냥 그 상황을 그대로 유지하면서 어두운 기운을 아예 안 뿜어낸다는 건데, 지속 가능한 플랜이 아닌 것 같습니다. 문제 상황이 해결되는 것도 아니고요.
  • face-to-face 소통이 생각보다 중요한 것 같습니다. 머리 깨질 것 같은 상황에서도 얼굴 보고 이야기 하면 생각보다 진정이 잘 되는 듯.
  • 그러니까 아무리 어려운 문제라도 일단 얼굴 마주보면서 대화를 하려고 하는 자세가 중요한 것 같습니다. 
  • 올해 제일 큰 실수는 그렇게 대화를 시도하다가 도화선을 건드려서 터지는 시나리오가 무서워서 그렇게 하지 않은 것이라고 생각합니다. 
  • 문제 상황을 같이 resolve 해야하는 상대를 "적"을 대하듯이 최악의 시나리오만 생각하면서 대하면 죽어도 해결 못합니다.
  • 보안 일 하면 adversarial mindset이 중요하다보니 자꾸 이 길로 빠지는 것 같은데 조심해야겠습니다... 어려워요
  • 어쨌든 본인을 위해서 하는 일이니 무리하지 않는 것도 중요한 것 같습니다. 본인이 과하게 무리하면 결국 좋은 매니징 못할 듯...
  • 근데 지금 이렇게 정리를 해도 이게 쉽지 않은 것은 맞아서 나중에 또 실수할 것 같습니다. 저도 이거 깨닫고 또 실수해서 ㅋㅋ;

돌고 돌아서 올해 이후로 제가 저 스스로 보는 방식에 대해서 많이 달라진 것 같습니다. 

  • 일단 생각보다 제가 허물이 엄청나게 많은 사람이라는 것을 느꼈습니다 
  • 이에 따라 "허물이 있는 사람들"을 보는 시선도 이전보다 훨씬 더 관용적이게 된 것 같습니다 
  • 이와 연결되는게, 예전에는 명예욕이라는 게 꽤 있었는데, 많이 사라졌고 아예 이제는 조용히 살고 싶은 욕심이 더 큽니다
  • 꽤 관련된 이야기로 최근에 dcinside 등 사이트에서 제 블로그가 링크 걸려 유입되는 경우가 있었는데, 이것도 꽤 스트레스더라구요.
  • 아무튼 올해 다양한 것을 겪으면서 조금 더 제 자신의 행동이나 말에 주의를 가해야겠다는 생각이 들었습니다. 파이팅!

 

재밌는 이야기 - 음악 / 스포츠 / 여행 등

음악

  • 외국 힙합을 조금 더 본격적으로 입문했습니다. 아직 부족하지만... 
  • 이 외에도 명반이라는 평가를 받는 음반들을 더 본격적으로 듣기 시작했습니다. 아직 부족하지만...
  • Vinyl/CD를 사기 시작했고 관련 기기들도 구매했습니다. 꽤 비싼 취미여서 얼마나 더 살지는 모르겠습니다. 
  • https://rkm0959.tistory.com/292
  • dj okawari 내한 공연에 가서 사진도 찍고 7인치 바이닐 사인도 받았습니다. 
  • 피아노 레슨을 받기 시작했습니다. 지금은 게임 OST를 치고 있고, 예를 들어 Re Aoharu의 쉬운 버전을 치고 있습니다.
    • 이제는 Paranoid Android 한 곡만 집중적으로 레슨 받기로 결정했습니다. 
  • 좋아하는 곡들: 가능하면 한 앨범에 한 곡
    • Through The Wire (Late Orchestration)
    • FEAR. (DAMN.)
    • Kingdom Hearts Key (SCARING THE HOES)
    • Saint Pablo (The Life of Pablo)
    • Motion Picture Soundtrack (Kid A)
    • Devil in a New Dress (My Beautiful Dark Twisted Fantasy)
    • Paranoid Android (OK Computer)
    • Real (good kid, m.A.A.d city)
    • Freee (KIDS SEE GHOSTS)
    • Luv(sic.) pt3 (Modal Soul)

스포츠

  • 돌고 돌아서 NBA 플레이오프만 열심히 본 것 같습니다. 요키치 우승해서 더 바라는 게 없습니다. 
    • 요키치 진짜 플레이오프 때 개잘하더라구요. 레이커스 상대로 보여준 서커스는 아직도 기억에 많이 남습니다. 
    • 레이커스도 골스 상대로 꽤 멋진 모습을 많이 보여줘서 재밌었습니다. 리브스의 버저비터는 명장면이네요.
    • 지미 버틀러가 밀워키 상대로 보여준 모습도 인상적이었습니다. 보스턴한테 역스윕 당할 뻔한 순간도 기억에 남네요.
    • 요키치가 MVP 받았어야 했던 것 같은데, 우승했으니 상관없습니다. 엠비드는 언제 2라딱을 멈출까요? 
  • 미국 스포츠에 대한 관심도가 확실히 떨어진 것 같아요. NFL 플레이오프에 한 번, NBA 플레이오프 때 한 번 관심 가지지 않을까...
  • 롤의 경우, 기억나는 이야기가 몇 가지 있습니다.
    • 5월에 MSI 결승이 도쿄 여행 중이어서, 비싼 료칸을 잡아서 거기서 온천과 동시에 즐길 생각이었습니다. 결승이 LPL 내전이 나오더라구요.
    • 롤드컵을 직관갔습니다. 8강에서 젠지/KT가 지는 것을 보고 (...) 4강에서 T1이 징동 이기는 것도 직관했습니다.
    • T1의 8강과 결승은 친구들과 모여서 봤습니다. 8강에서 폼이 생각보다 너무 좋아서 기대를 많이 하게 되었습니다. 
    • 역사적인 장면을 보게 되어 기쁘고, 꽤 오래 원했던 페이커의 4번째 우승을 보게 되어 기쁩니다. 재계약도 기쁩니다. 

여행

  • 2월, 5월, 8월에 도쿄, 4월에 몬테네그로, 8월에만 미국 두 번, 9월에 런던을 방문했습니다. 많이도 갔네요. 재밌었습니다. 
  • 5/8월에 일본에 거주하는 CTF러들 많이 만나서 기뻤습니다. ptr-yudai, keymoon, icchy, xornet, minaminao, y011d4.
  • 도쿄 돔과 펫코 파크에서 야구를 직관했습니다. 두 경기 다 홈 팀이 이겨서 좋았습니다. 
  • 8월에 요코하마에서 열린 포켓몬 월드챔피언십 현장에 방문했습니다. 지인이 대표인 덕에 관전도 할 수 있었습니다. 

게임 

  • 1월 즈음에 유희왕 마스터듀얼을 시작했다가 티아라멘츠 나왔을 때 접었습니다. 
    • 개구리 스프라이트, 패털이 아다마시아, 참기 토커, 마돌체, 봄화정 마돌체 돌렸습니다
    • 다시 시작할까 싶어서 보니까 금제가 굉장히 많이 바뀌었더라구요 ㅋㅋ;
    • 마돌체를 엔젤리 나올 때부터 굴렸습니다 (그 당시에는 TG 마돌체를 굴렸습니다)
    • 5월에 아키하바라에서 티아라미스 카드를 슈퍼 레어로 하나 사서 지갑에 부적으로 넣어놓고 있습니다. 
  • 마리오 원더 100%를 했습니다. 재밌었습니다. 

otaku shit

  • 애니는 많이는 안 보고 최애의 아이와 호리미야 정도만 본 것 같습니다. 
  • 4월에 블루 아카이브 스토리를 알게 되서 관심 가지게 되었습니다. 근데 겜안분인게 레전드
  • 5월에 도쿄 가서 bar u.n.owen을 여러 번 방문했습니다. 재밌었어요. 
  • 8월에 코미케 1일차를 즐겼습니다. 다만 그 날 bar u.n.owen에서 술을 너무 먹고 노래방에서 밤 새서 2일차는 못 갔습니다. 
  • 생각보다 이런 컨텐츠를 100% 즐기기에는 너무 라이트 오타쿠인 것 같지만 그냥 그러려니 하기로 했습니다.
  • 10월 일러스타페스, 12월 AGF, 12월 서코 모두 갔습니다. 굿즈 꽤 많이 샀습니다. 
  • 블루 아카이브 신용카드를 발급받았습니다. 지갑에 이거랑 티아라미스 카드 포함해서 부적이 다양하게 있습니다 ㅎ_ㅎ
  • 블루 아카이브 현대백화점 콜라보에 갔습니다. 아비도스 옷 잘 입고 있습니다. 
  • 블루 아카이브 오케스트라를 보러 갔습니다. 오랜만에 이런 거 보러가서 즐거웠어요. 
  • 스즈메의 문단속을 오케스트라와 함께 공연한 필름 콘서트를 보러 갔습니다. 재밌었습니다. 
  • 일본어 공부를 핌슬러를 통해서 하고 있는데, 꾸준하게 하고 있지는 못하는 것 같아서 스스로에게 아쉽습니다.

이 외에도 다이어트에 성공해서 꽤 건강한 상태로 돌아왔습니다! 올해 한 일 중 꽤 성공적인 것...

 

2024년을 바라보며 

암호 공부

  • 일단 ZKP 관련해서 아직도 rough 하게 아는 지식을 명확하게 하는 작업을 빠르게 해야 할 것 같습니다.
  • 그 이후로는 계속 ZKP만 보기보다는 MPC와 MPC-in-the-head, 그리고 HE를 보고자 합니다.
  • 그리고 암호 관련 엔지니어링에도 조금 더 손을 대보고 싶습니다. 아무래도 아직 코드를 직접 짜는 게 안 익숙해서...
  • 올해는 공부한 논문들에 대해서 간략하게라도 영어로 어디엔가 정리하는 습관을 들이고자 합니다. hackmd를 쓰지 않을까 싶어요.
  • 연구실 연락을 슬슬 해봐야하나 싶기도 하면서도 좀 두렵기도 합니다.
  • ZKP 보안 관련해서 좀 명확하게 이름을 남기고 싶습니다. 동시에 Smart Contract Security도 조금 더 잘해지고 싶네요.

유학 준비 

  • GRE와 TOEFL은 무조건 올해 치워야 합니다. 2025년 겨울에 원서를 쓰게 될 것 같습니다.

취미 생활

  • 블루 아카이브 관련 구경이나 하면서 주변 친구들 보는 애니메이션이나 보면 될 것 같습니다.
  • 라프텔 결제해놓고 거의 안 써서 아쉽습니다. 적당히 취미로 보는 정도로 사용하는 걸 목표로 합니다. 
  • 피아노는 4월까지는 결제되어 있으니 그때까지 최대한 다양한 곡을 맛보는 것을 목표로 하고 있습니다.
  • 일본어 공부는 계속 꾸준히 하고자 합니다. N3 정도 수준은 만들어 놓을 수 있으면 좋겠습니다. 
  • 음악을 자꾸 익숙한 것만 듣게 되는데 각 잡고 집중해서 앨범 하나를 쭉 들을 수 있으면 좋겠습니다. 더 다양한 음악을 듣고 싶어요.
  • Paper Mario TTYD가 2024년에 스위치로 나와서 그거 100%를 해야겠습니다

기타

  • 2024년에 군대가 끝납니다. 이때까지 무사히 보낼 수 있으면 좋겠습니다.
  • 일본에서 한 달 살 계획을 하고 있습니다. 11월이나 12월에 도쿄로 갈까 싶어요.
  • 사람들 더 많이 만나고 더 다양한 경험을 하면서 살면 좋을 것 같습니다. 그게 제일 행복한 것 같아요. 
  • 좀 더 적극적으로 대화할 수 있는 외향적인 사람이 되면 좋겠습니다
  • 운전면허를 따야합니다
  • 뭔가 옷을 조금 더 잘 입고 다닐 수 있으면 좋겠다는 생각도 드네요

'미래 계획 및 근황' 카테고리의 다른 글

Joining Succinct  (1) 2024.06.13
2022: Quick Retrospective  (6) 2022.12.28
Recent Updates  (4) 2022.08.12
근황 보고  (4) 2022.05.18
6월 및 7월 초 정리  (4) 2021.07.15

https://infossm.github.io/blog/2023/11/26/Folding/

 

Folding Part 1: ProtoStar

이 글에서는 ZKP에서 사용되는 테크닉인 folding의 두 대표적인 논문인 ProtoStar와 HyperNova 중 ProtoStar에 대해서 다룹니다. https://eprint.iacr.org/2023/620.pdf Folding이란 무엇이며, ProtoStar의 목표는 무엇인가

infossm.github.io

 

https://infossm.github.io/blog/2023/10/22/MultilinearPCS/

 

Multilinear PCS from Univariate PCS

저번 포스팅에서는 Multilinear Polynomial에 대한 linear-time commitment 중 하나인 Brakedown에 대해서 알아보았습니다. Sumcheck 관련 기법들이 떠오르면서, Multilinear Polynomial의 commitment에 대한 기법들이 더욱

infossm.github.io

 

'Cryptography' 카테고리의 다른 글

Folding Part 2: HyperNova  (0) 2024.01.03
Folding Part 1: ProtoStar  (0) 2023.12.01
Brakedown Overview  (0) 2023.10.13
Monolith Hash Function  (0) 2023.09.30
[Axiom OS Project] Implementing Poseidon2 & AES-ECB for Verifiable Encryption  (0) 2023.06.14

'CTF' 카테고리의 다른 글

ACSC 2024: Strange Machine (4 solves)  (0) 2024.03.31
CODEGATE 2023 Finals - The Leakers (1 solve)  (1) 2023.08.25
ACSC 2023 Writeups  (0) 2023.02.26
HackTM CTF Writeup  (0) 2023.02.22
BlackHat MEA Finals  (0) 2022.11.21

We participated in Paradigm CTF with KALOS team members and some friends (minaminao, taek, epist, gss1, pia).

 

During the competition, there were 2 challenges with the tag "cryptography" and I ended up getting first blood on both.

 

Oven

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
63
#!/usr/bin/env python3
from Crypto.Util.number import *
import random
import os
import hashlib
 
FLAG = os.getenv("FLAG""PCTF{flag}").encode("utf8")
FLAG = bytes_to_long(FLAG[5:-1])
assert FLAG.bit_length() < 384
 
BITS = 1024
 
 
def xor(a, b):
    return bytes([i ^ j for i, j in zip(a, b)])
 
 
# This doesn't really matter right???
def custom_hash(n):
    state = b"\x00" * 16
    for i in range(len(n) // 16):
        state = xor(state, n[i : i + 16])
 
    for _ in range(5):
        state = hashlib.md5(state).digest()
        state = hashlib.sha1(state).digest()
        state = hashlib.sha256(state).digest()
        state = hashlib.sha512(state).digest() + hashlib.sha256(state).digest()
 
    value = bytes_to_long(state)
 
    return value
 
 
def fiat_shamir():
    p = getPrime(BITS)
    g = 2
    y = pow(g, FLAG, p)
 
    v = random.randint(22**512)
 
    t = pow(g, v, p)
    c = custom_hash(long_to_bytes(g) + long_to_bytes(y) + long_to_bytes(t))
    r = (v - c * FLAG) % (p - 1)
 
    assert t == (pow(g, r, p) * pow(y, c, p)) % p
 
    return (t, r), (p, g, y)
 
 
while True:
    resp = input("[1] Get a random signature\n[2] Exit\nChoice: ")
    if "1" in resp:
        print()
        (t, r), (p, g, y) = fiat_shamir()
        print(f"t = {t}\nr = {r}")
        print()
        print(f"p = {p}\ng = {g}\ny = {y}")
        print()
    elif "2" in resp:
        print("Bye!")
        exit()
 
cs

 

So we are given a random signature oracle. To be precise, we know $t, r, p, g, y$ such that $$c = \text{hash}(g, y, t), \quad r \equiv (v - c \cdot flag) \pmod{p-1}$$ The key part I used is that we know $c, r, p$ and that $flag < 2^{384}$ as well as $v < 2^{512}$. In other words, we are finding the $0 < flag < 2^{384}$ such that $c \cdot flag + r \pmod{p-1}$ is less than $2^{512}$. This is a classic task suitable for lattice reduction (a bit overkill, but it is) and similar tricks have appeared in CTFs so much that I have a whole repository on this (https://github.com/rkm0959/Inequality_Solving_with_CVP)

 

A good heuristic to why this would work is that the "probability" of a value $flag$ satisfying $c \cdot flag + r \pmod{p-1} < 2^{512}$ would be around $2^{512} / p$, which is far less than $1/2^{384}$ as $p$ is 1024 bits. This means that there would be a unique $flag$ that satisfies our needs. 

 

To understand how to solve this "linear inequality with modulo" task, see https://rkm0959.tistory.com/188 (korean).

 

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
from sage.all import * 
from pwn import *
from Crypto.Util.number import GCD
 
def ceil(n, m): # returns ceil(n/m)
    return (n + m - 1// m
 
def is_inside(L, R, M, val): # is L <= val <= R in mod M context?
    if L <= R:
        return L <= val <= R
    else:
        R += M
        if L <= val <= R:
            return True
        if L <= val + M <= R:
            return True 
        return False
 
def optf(A, M, L, R): # minimum nonnegative x s.t. L <= Ax mod M <= R
    if L == 0:
        return 0
    if 2 * A > M:
        L, R = R, L
        A, L, R = M - A, M - L, M - R
    cc_1 = ceil(L, A)
    if A * cc_1 <= R:
        return cc_1
    cc_2 = optf(A - M % A, A, L % A, R % A)
    return ceil(L + M * cc_2, A)
 
# check if L <= Ax (mod M) <= R has a solution
def sol_ex(A, M, L, R):
    if L == 0 or L > R:
        return True
    g = GCD(A, M)
    if (L - 1// g == R // g:
        return False
    return True
 
## find all solutions for L <= Ax mod M <= R, S <= x <= E:
def solve(A, M, L, R, S, E):
    # this is for estimate only : if very large, might be a bad idea to run this
    print("Expected Number of Solutions : ", ((E - S + 1* (R - L + 1)) // M + 1)
    if sol_ex(A, M, L, R) == False:
        return []
    cur = S - 1
    ans = []
    num_sol = 0
    while cur <= E:
        NL = (L - A * (cur + 1)) % M
        NR = (R - A * (cur + 1)) % M
        if NL > NR:
            cur += 1
        else:
            val = optf(A, M, NL, NR)
            cur += 1 + val
        if cur <= E:
            ans.append(cur)
            # remove assert for performance if needed
            assert is_inside(L, R, M, (A * cur) % M)
            num_sol += 1
    print("Actual Number of Solutions : ", num_sol)
    return ans
 
# conn = remote("oven.challenges.paradigm.xyz", 1337)
# conn.interactive()
 
 
import hashlib
from Crypto.Util.number import *
 
def xor(a, b):
    return bytes([i ^ j for i, j in zip(a, b)])
 
 
# This doesn't really matter right???
def custom_hash(n):
    state = b"\x00" * 16
    for i in range(len(n) // 16):
        state = xor(state, n[i : i + 16])
 
    for _ in range(5):
        state = hashlib.md5(state).digest()
        state = hashlib.sha1(state).digest()
        state = hashlib.sha256(state).digest()
        state = hashlib.sha512(state).digest() + hashlib.sha256(state).digest()
 
    value = bytes_to_long(state)
 
    return value
 
= 93427683041905342461173547022600938643986887324972032834291939142561139490252265979618477433690413153065906221518481848227204925109596682649424431709625280133746760813834179099858484483652348113289609400674325409313902686091936601023976041128497642819529787946866157016217668015647432593957212819330706662552
= 118742916848068745441234425121114897870051115198012668332112268094669581171444207495264796187702240967886273172282936547873545351825602051457018801135490983227564157979548997162173927440795170927696473299845487953514965643146540163956783643164820892016837035894476678034631205573666641222349277397600109205124
 
= 126549310493151963326469876679724603661026366918265538391139061164994266707511395259083420603797826570096038735637035531704734213415007496749352216356840971790966322793226620694976878837854388424723443760043794854992519120259435122442271146978894991534180108105270279798030108380275673703977920882358759270081
= 2
= 101749117219274577198619316763589342740512542428910664337482178675253076795143579139493733233731229068585593656754291831105189837876269162333709022495477051005897166911586115461217424920314778304390479804373263955110732503700846048681418836722374515970914402818776396927744121752161147483063673287114906716300
 
= custom_hash(long_to_bytes(g) + long_to_bytes(y) + long_to_bytes(t))
 
//= 15 
lmao = r % 15
= (r - r % 15// 15 
 
= (p - 1// 15 
 
print(GCD(c, M))
lst = solve(c, M, (-r) % M , ((1 << 512// 15 - r + M) % M, 01 << 384)
 
print(lst)
 
print(long_to_bytes(10803675063719384436548220153547010608867399889700922150272564339681282264952460761794626241561264720352594960927090))
 
cs

 

 

Dragon Tyrant

The codebase is quite large, so I can't upload it all here. A quick summary - 

  • The goal of the challenge is to slay the dragon
  • To slay the dragon, one has get an NFT with max attack/defense, and predict the dragon's moves 60 times in a row.
  • The dragon's moves, as well as the basic stats of a generated NFT, is done with a weird elliptic curve based RNG.
  • To get max attack/defense, one can buy items from an item shop
  • However, getting the max attack sword legit is too expensive
  • but it suffices to buy items from a shop that has the same extcodehash as the provided one. 

Let's start with getting the max attack and defense. We just need matching extcodehash - so whatever we do in the constructor doesn't matter, as long as we return the same code. Therefore we can do some nice tricks as follows.

 

1
2
3
4
5
6
7
8
9
10
11
contract ItemShop2 is ItemShop {
    constructor(bytes memory code) {
        // write this
        _itemInfo[4= ItemInfo({name"A", slot: EquipmentSlot.Weapon, value: type(uint40).max, price: 0}); // example
        _itemInfo[5= ItemInfo({name"B", slot: EquipmentSlot.Shield, value: type(uint40).max, price: 0}); // example
        _mint(msg.sender, 41"");
        _mint(msg.sender, 51"");
        assembly { return ( add(code, 0x20), mload(code)) }
    }
}
 
cs

 

Now we can equip this accordingly to get max attack/defense. We now have to predict the moves. 

When the off-chain entity resolves the randomness, it first generates the random values for the mints' traits.

Only after that, it generates the random value for the dragon's move. This can be seen in the code below.

 

1
2
3
4
5
6
7
8
9
function resolveRandomness(bytes32 seed) external override {
        if (msg.sender != address(factory.randomnessOperator())) {
            revert Unauthorized(msg.sender);
        }
 
        _lastOffchainSeed = seed;
        uint256 nextRound = _resolveMints();
        _resolveFight(nextRound);
    }
cs

 

We can also fetch the traits, as the NFT contract provides a public function for it. This implies that we can fetch all the previously generated values for the off-chain provided seed. In other words, if we can compute $\text{rand}(seed, i + 1)$ from $\text{rand}(seed, i)$, we would be done. 

 

1
2
3
function _generateRandomness(uint256 round) internal view returns (bytes32 rand) {
        rand = randomness.generate(_lastOffchainSeed, round + 1);
    }
cs

 

Now let's look at the randomness itself. 

 

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.19;
 
import "./OwnedUpgradeable.sol";
import "./Interfaces.sol";
 
contract Randomness is IRandomness {
    error AlreadySet();
    // https://eips.ethereum.org/EIPS/eip-197 Y^2 = X^3 + 3
    // a generator of alt_bn128 (bn254)
 
    uint256 public constant Gx = 1;
    uint256 public constant Gy = 2;
    uint256 public immutable Px;
    uint256 public immutable Py;
    uint256 public immutable Qx;
    uint256 public immutable Qy;
    uint256 public constant fieldOrder =
        uint256(21888242871839275222246405745257275088696311157297823662689037894645226208583);
    uint256 public constant groupOrder =
        uint256(21888242871839275222246405745257275088548364400416034343698204186575808495617);
 
    constructor() {
        uint256 P_x;
        uint256 P_y;
        uint256 Q_x;
        uint256 Q_y;
 
        bytes32 r = bytes32(uint256(0x123456789));
 
        assembly {
            mstore(0x80, Gx)
            mstore(0xa0, Gy)
            mstore(0xc0, r)
            if iszero(staticcall(gas(), 0x070x800x600x800x40)) { revert(00) }
            P_x := mload(0x80)
            P_y := mload(0xa0)
 
            mstore(0x80, Gx)
            mstore(0xa0, Gy)
            mstore(0xc0, r)
            mstore(0xc0, keccak256(0xc00x20))
            if iszero(staticcall(gas(), 0x070x800x600x800x40)) { revert(00) }
            Q_x := mload(0x80)
            Q_y := mload(0xa0)
        }
 
        Px = P_x;
        Py = P_y;
        Qx = Q_x;
        Qy = Q_y;
    }
 
    /// @notice Generates a sequence of random numbers from an initial seed
    /// @param seed The initial seed
    /// @param rounds The round to generate
    /// @return rand The generated randomness for the round
    function generate(bytes32 seed, uint256 rounds) external view override returns (bytes32 rand) {
        uint256 Q_x = Qx;
        uint256 Q_y = Qy;
        uint256 P_x = Px;
        uint256 P_y = Py;
        assembly {
            mstore(0x00, P_x)
            mstore(0x20, P_y)
            mstore(0x40, seed)
            for { let i := 0 } lt(i, rounds) { i := add(i, 1) } {
                if iszero(staticcall(gas(), 0x070x000x600x400x40)) { revert(00) }
            }
            mstore(0x00, Q_x)
            mstore(0x20, Q_y)
            if iszero(staticcall(gas(), 0x070x000x600x400x40)) { revert(00) }
            rand := mload(0x40)
            mstore(0x400x80)
        }
    }
}
 
cs

 

So it first takes $r$ as 0x123456789 and sets $P = r \cdot G$ and $Q = \text{hash}(r) \cdot G$. Then, the randomness is generated by iterating $seed \leftarrow (seed \cdot P).x$ for $round$ number of times and finishing with $out \leftarrow (seed \cdot Q).x$. 

 

Now we see the idea - since we know the $(seed \cdot Q).x$ as the output, one can recover $seed \cdot Q$ where $seed$ is the result of $round$ iterations. Since we know the discrete-logarithm relations between $P$ and $Q$, this means that we can also recover $seed \cdot P$ - and taking the $x$ coordinate here would be the result of $round + 1$ iterations. Now doing $out \leftarrow (seed \cdot Q).x$ once again would be sufficient to get the randomness result for $\text{rand}(seed, round + 1)$. We have our theoretical exploit! Now on to the implementation.

 

To do this in a smart contract, the only hard part would be to recover the full elliptic curve point from the $x$ coordinate alone. To do this you need a modular square root, but since $p \equiv 3 \pmod{4}$ it's easy, (no Tonelli-Shanks) simply raise to $(p+1)/4$th power.  

 

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.13;
 
import {Script, console2} from "forge-std/Script.sol";
import "../test/Counter.t.sol";
 
import "../src/ItemShop.sol";
import "../src/ItemShop2.sol";
import "../src/Challenge.sol";
 
 
contract Exploiter {
    Challenge public challenge;
    NFT public nft;
    ItemShop public itemShop;
    Factory public factory;
    ItemShop2 public itemShop2;
    Exploiter public lmao;
    uint256 public cnter = 0;
     uint256 public constant fieldOrder =
        uint256(21888242871839275222246405745257275088696311157297823662689037894645226208583);
    uint256 public constant groupOrder =
        uint256(21888242871839275222246405745257275088548364400416034343698204186575808495617);
 
    function exploit_part_1(address chall) external {
        challenge = Challenge(chall);
        factory = challenge.FACTORY();
        nft = challenge.TOKEN();
        itemShop = challenge.ITEMSHOP();
        itemShop2 = new ItemShop2(address(itemShop).code);
        itemShop2.setApprovalForAll(address(nft), true);
        address[] memory myself = new address[](1);
        myself[0= address(this);
        nft.batchMint(myself);
    }
 
    function exploit_part_2() external {
        address[] memory myself = new address[](1);
        myself[0= address(this);
        nft.batchMint(myself);
        nft.fight(10);
    }
 
    function onERC721Received(address sender, address from, uint256 tokenId, bytes memory data) external returns (bytes4) {
        cnter += 1;
        if(cnter == 1) {
            nft.equip(tokenId, address(itemShop2), 4);
            nft.equip(tokenId, address(itemShop2), 5);
        }
        return this.onERC721Received.selector;
    }
 
    function modExp(uint256 _b, uint256 _e, uint256 _m) public returns (uint256 result) {
        assembly {
            let pointer := mload(0x40)
 
            mstore(pointer, 0x20)
            mstore(add(pointer, 0x20), 0x20)
            mstore(add(pointer, 0x40), 0x20)
 
            mstore(add(pointer, 0x60), _b)
            mstore(add(pointer, 0x80), _e)
            mstore(add(pointer, 0xa0), _m)
 
            let value := mload(0xc0)
 
            if iszero(call(gas(), 0x050, pointer, 0xc0, pointer, 0x20)) {
                revert(00)
            }
 
            result := mload(pointer)
            mstore(0x40, pointer)
        }
    }
 
    function getInput(FighterVars calldata attacker, FighterVars calldata attackee) external returns (uint256 inputs) {
        Trait memory trait = nft.traits(2);
 
        uint256 prev_rand = 0;
        prev_rand += uint256(trait.rarity);
        prev_rand += uint256(trait.strength) << 16;
        prev_rand += uint256(trait.dexterity) << 56;
        prev_rand += uint256(trait.constitution) << 96;
        prev_rand += uint256(trait.intelligence) << 136;
        prev_rand += uint256(trait.wisdom) << 176;
        prev_rand += uint256(trait.charisma) << 216;
 
        // recover the elliptic curve point
        uint256 cube_3_3 = modExp(prev_rand, 3, fieldOrder) + 3;
        uint256 y_val = modExp(cube_3_3, (fieldOrder + 1/ 4, fieldOrder);
 
        uint256 interim;
        assembly {
            interim := mload(0x40)
        }
 
        assembly {
            let pointer := mload(0x40)
            mstore(pointer, prev_rand)
            mstore(add(pointer, 0x20), y_val)
            mstore(add(pointer, 0x40), 0x200ac28172d3dfaf595636a5d34fc6a98f3168b32317278ab95d95792e3b4f8f)
            if iszero(staticcall(gas(), 0x07, pointer, 0x60, pointer, 0x40)) { revert(00)}
            interim := mload(pointer)
            mstore(0x40, pointer)
        }
 
        uint256 Qx =   2771061477252358712132284804733770040260252456558485434530149143843066948317;
        uint256 Qy = 21636887117896825552852388732829976843920120171647088092176094089927511555925;
        assembly {
            let pointer := mload(0x40)
            mstore(pointer, Qx)
            mstore(add(pointer, 0x20), Qy)
            mstore(add(pointer, 0x40), interim)
            if iszero(staticcall(gas(), 0x07, pointer, 0x60, pointer, 0x40)) { revert(00)}
            interim := mload(pointer)
            mstore(0x40, pointer)
        }
 
        return type(uint256).max - interim;
    }
 
 
    function onERC1155Received(address, address, uint256, uint256, bytes calldata)
        external
        pure
        returns (bytes4)
    {
        return this.onERC1155Received.selector;
    }
 
    function onERC1155BatchReceived(address, address, uint256[] calldata, uint256[] calldata, bytes calldata)
        external
        pure
        returns (bytes4)
    {
        return this.onERC1155BatchReceived.selector;
    }
}
 
 
contract CounterScript is Script {
    Challenge challenge;
    NFT nft;
    ItemShop itemShop;
    Factory factory;
    ItemShop2 itemShop2;
    Exploiter lmao;
    uint256 public constant fieldOrder =
        uint256(21888242871839275222246405745257275088696311157297823662689037894645226208583);
    uint256 public constant groupOrder =
        uint256(21888242871839275222246405745257275088548364400416034343698204186575808495617);
 
    function setUp() public {}
 
    function run() public {
        vm.startBroadcast();
        challenge = Challenge(0x4c2f201aFd08F986BDeed4907C263795c1510F75);
 
        /*lmao = new Exploiter();
        console2.log(address(lmao));
 
        lmao.exploit_part_1(address(challenge));
        vm.stopBroadcast();*/
 
 
        
        lmao = Exploiter(0xf25888e0B386Ed0739B0d2D77CE68B6e1E0583b5);
        console2.log(lmao.cnter());
        
        lmao.exploit_part_2();
        console2.logBool(challenge.isSolved());
        
        vm.stopBroadcast();
        
    }
}
 
cs

 

'Blockchain Security' 카테고리의 다른 글

Curta / Plonky2x Audit Report  (0) 2024.02.27
zkSummit11 @ Athens  (0) 2024.02.24
Scroll's Security Measure Seminar  (0) 2023.10.25
Scroll zkEVM Audit Report  (0) 2023.10.17
ZKP Security Seminar @ SpearbitDAO  (1) 2023.07.27

https://twitter.com/Scroll_ZKP/status/1716781095138861158

 

X에서 Scroll 📜 님

This week, we'll be hosting an online webinar to dive into our security measures, and you're invited! We'll be joined by auditing collaborators from @immunefi, @zellic_io, @trailofbits, and @OpenZeppelin. 🗓 Save the date: October 25th, at 9:00AM EST. ht

twitter.com

 

'Blockchain Security' 카테고리의 다른 글

zkSummit11 @ Athens  (0) 2024.02.24
Paradigm CTF 2023: "Cryptography Challenges"  (0) 2023.10.30
Scroll zkEVM Audit Report  (0) 2023.10.17
ZKP Security Seminar @ SpearbitDAO  (1) 2023.07.27
A fun story on "Membership Proofs"  (0) 2022.12.07

https://github.com/kalos-xyz/Publications/blob/main/audit-reports-english/Scroll_zkEVM_-_Audit_Report.pdf

https://github.com/kalos-xyz/Publications/blob/main/audit-reports-english/Scroll_zkEVM_-_Part_2_-_Audit_Report.pdf

 

제가 참가한 보안감사 리포트가 공개되었습니다 :)