Optimization

  • 올해 초에 Ernest Ryu 교수님의 랩실에서 서포트 역할을 맡아서 논문 작업을 하나 도왔습니다. 
  • ICML oral로 accept 되었는데 2저자기도 하고 여러모로 제대로 못 도와드린 것 같아서 아쉬움이 있습니다. 
  • 논문은 진짜 재밌습니다. 1저자분과 교수님의 아이디어들이 되게 신기했습니다. 더 팔 게 많은 방향인 것 같아요.
  • 저 논문 관련된 태스크가 끝난 뒤로, 병특과 랩실을 병행하기 어려울 것 같아서 일단 일시정지한 상태입니다.
  • PEPit에 기여를 했습니다. 교수님 랩실에서 나온 논문에서 나온 알고리즘들 몇 개를 추가했어요.
  • 암호학 쪽으로 더 공부를 열심히 할 것 같고, 가끔 랩실 논문 리뷰할 것 있으면 리뷰할 것 같아요. 코드 감사하듯 리뷰하면 재밌습니다.

논문 링크: https://arxiv.org/abs/2202.05501

 

Continuous-Time Analysis of Accelerated Gradient Methods via Conservation Laws in Dilated Coordinate Systems

We analyze continuous-time models of accelerated gradient methods through deriving conservation laws in dilated coordinate systems. Namely, instead of analyzing the dynamics of $X(t)$, we analyze the dynamics of $W(t)=t^α(X(t)-X_c)$ for some $α$ and $X_c

arxiv.org

 

Zero Knowledge

 

GitHub - rkm0959/rkm0959_presents: Presentations by rkm0959

Presentations by rkm0959. Contribute to rkm0959/rkm0959_presents development by creating an account on GitHub.

github.com

  • 이 발표로 저를 알게 된 분들이 꽤 있는 것 같습니다. 이런 경로로 저를 아는 분들이 생기는 건 좋은 것 같습니다. 
  • 저기서 시작해서 Groth16, PLONK, Recursive SNARK 쪽을 어느 정도 공부한 것 같습니다.
  • 0xPARC 사람들과 정말 고맙게도 다시 연락이 닿아서 관련 이야기를 할 수 있는 채널이 늘어났습니다. 
  • ZK-ZK-SEL이라고 한국에서 ZK 이해도 높으신 분들과 이야기를 할 수 있는 채널이 생겼습니다. 
  • Open Source Contributon에 참여했습니다. 이론적인 건 괜찮은데 제가 아직 구현/개발쪽이 문제같습니다.
  • 0xPARC 덕분에 9월에 Stanford 쪽으로 가서 Research Workshop에 참가할 수 있었습니다. 재밌었어요!
  • 약간 아쉽게 끝났지만 (SOTA와 사용하는 아이디어가 비슷하기는 해서) Lookup Argument 관련 연구도 했습니다.
  • https://zkresear.ch/t/new-lookup-argument/32
 

New Lookup Argument

New Lookup Argument Authors: rkm0959 (Gyumin Roh), Wei Dai, Mark (majabbour), Andrew He This work started from the problems Haichen Shen and Ying Tong presented at the ETH x ZK Research Workshop in Stanford. We thank them and many others from the research

zkresear.ch

 

GitHub - rkm0959/rkm0959_presents: Presentations by rkm0959

Presentations by rkm0959. Contribute to rkm0959/rkm0959_presents development by creating an account on GitHub.

github.com

  • Software Membership 쪽에 ZK 관련 fundamental을 꽤 올렸습니다. 
  • 내년 목표는 일단 ZK Protocol 관련 SOTA 논문을 다 밀고, Thaler 책을 다 읽고, 개발 쪽에 손이 익도록 하는 것입니다. 
  • 이러려면 결국 Rust 공부가 병행되어야 할 것 같습니다. 더 미루면 안될 것 같아요. Go도 조금 손에 익었으면 합니다. 
  • 다른 암호 분야 이야기도 여기서 하자면, https://toc.cryptobook.us/ 밀고 격자 공부를 조금 더 해야할 것 같네요.
  • 솔직히 블록암호나 다른 분야에 특별한 관심까지는 없어서 일단 ZK 쪽에 구경이나 더 하는걸로...
  • 0xPARC에서 같이 개발 연습할 기회는 많은데 이번에는 좀 제대로 잡았으면 좋겠네요. ZK 관련 보안감사도 있으면 좋을 듯.

 

Security & CTF

 

CODEGATE CTF 2022: Look It Up Writeup | Deeper Look at PLOOKUP

Introduction On November 7th to 8th, the annual cybersecurity conference called CODEGATE was held in South Korea. Alongside with, a 24 hour CTF was held, where the world’s top cybersecurity researchers solved various challenges on pwn, reverse engineerin

zkresear.ch

  • 대회 참가하러 해외에 나갈 수 있어서 좋았습니다. 
  • DEFCON에서 해외 지인도 꽤 많이 볼 수 있어서 좋았어요. 근데 기여를 못하는 게 항상 아쉽습니다.
  • BlackHat MEA에서는 기여도 할만큼 하고 상금도 든든하게 받아서 좋았습니다. 사우디 가는 것도 좋구요. 
  • 내년 초에 SECCON을 치러 일본으로 갑니다. 진짜 오랜만에 일본으로 가게 되어서 좋습니다. 
  • 버스 탑승으로 NSUCRYPTO 2022를 우승했습니다. 진짜 버스 탑승 제대로 했습니다. 
  • Paradigm CTF를 조금 열심히 쳤어야 했는데 그때 담원 vs T1 플옵 경기보고 속이 뒤집어져서 진짜 아파서 못함 ㅋㅋ
  • CODEGATE 컨퍼런스에서 발표했습니다. 나름 신기한 경험이었어요. 
  • https://github.com/rkm0959/rkm0959_presents/blob/main/PriceOracle-CODEGATE2022.pdf
 

GitHub - rkm0959/rkm0959_presents: Presentations by rkm0959

Presentations by rkm0959. Contribute to rkm0959/rkm0959_presents development by creating an account on GitHub.

github.com

  • 금융보안원에서 블록체인에 대한 강의를 할 일이 있었습니다. 이것도 재밌었어요.
  • 회사 동료분과 함께 0-day 버그를 찾은 경험이 조금 늘어났습니다. (THORChain, ChainSafe, etc)
  • 현재 회사에서도 보안감사 일을 하고 있습니다. 아직까지는 큰 문제없이 잘하고 있는 것 같아서 다행입니다. 
  • 내년에도 계속 대회 출제를 할 수 있으면 좋겠습니다. 출제가 확실히 재밌기는 해서....
  • Super Guesser에서 뭔가 재밌는 일을 하게 될수도 있을 것 같은데 이것도 잘 되면 좋을 것 같아요. 
  • Code4rena 같은 대회나 ImmuneFi 버그 헌팅도 고려는 하고 있는데 사실 고르라고 하면 암호 공부할 것 같기는 합니다.
  • 옛날에는 pwn/web/rev를 공부하는 것에 대한 로망이 있었는데 솔직히 제가 지금 시작하는 건 별로인 것 같다는 결론을 내렸습니다.

 

"Macro" Timeline

  • 1~2월: 작년 말에 좀 일이 있어서 멘탈이 날라갔는데 복구하면서 랩실 작업에 집중했습니다. 
  • 3월: 이직하기로 결정하고 갈 곳들에게 컨택하고 절차를 밟았습니다.
    • 이직 이유는 트레이딩이 너무 어려워서 + 보안 일하는 게 재밌어보이고 적성도 맞을 것 같고 제 미래에도 도움이 될 것 같아서 
    • 여기서 어디로 이직을 할 것인지를 가지고 고민을 해야 했는데 진짜 정신나갈 것 같았습니다. 4월에 훈련소여서 시간이 없었어요.
    • 내린 선택에 대한 후회를 한 번도 안했냐고 물으면 그건 거짓말인데, 결국 생각하고 나면 결론이 대충 "이미 선택을 했으니까 내가 그 선택을 맞는 선택으로 만들기 위해서 노력하자"여서... 병특인만큼 이제 이직을 하더라도 엄청 신중하게 해야하는 게 맞으니까요. 다양한 길이 열려있고 좋게 봐주시는 분이 계시는 건 항상 감사한 일입니다. 더 노력해야겠어요 :) 어쨌든 지금은 "나만 잘하면 되는 환경"이 세팅된 상황 같아서 다행입니다.
  • 4월: 훈련소에 갔습니다. 여기서 공부를 조금 더 열심히 했으면 좋았을 것 같지만 솔직히 그냥 끝난 게 다행입니다.
  • 5월: Terra 사태가 터졌고 (저는 제 전재산 70%를 UST로 들고 있었는데 0.994에 다 팔았습니다) 저는 이직을 했습니다. MSI 보러 부산감. 
  • 6월: 이때부터는 Macro적인 건 특별히 없고, 그냥 회사에서 일을 했습니다 ㅋㅋㅋㅋ
  • 7월: 이때부터 본격적으로 Security Audit 일에 들어갔습니다. 이때 Open Source Contributon도 있었습니다.
  • 8월: DEFCON에 다녀온 게 메인 이벤트 같네요. ZK-ZK-SEL 분들도 이때 즈음에 만나서 같이 이야기하게 되었습니다. 
  • 9월: Stanford에 다녀온 게 메인 이벤트. 이때 Lookup Argument 연구를 조금 했고 회사일도 이때 재밌었어요.
  • 10월: NSUCRYPTO도 나갔는데 이때 여러가지로 고민이 많았던 기억이 있습니다. 사실 롤드컵 보느라 인생을 삭제시켰습니다.
    • 그거와 별개로 이때 회사 근처에 아지트를 하나 구했습니다. 디테일은 생략. 아무튼 잘 쓰고 있습니다. 
  • 11월: BlackHat MEA 다녀온 게 메인 이벤트. 근데 이때도 솔직히 약간 인생이 뇌절이긴 했어요 ㅋㅋㅋㅋㅋ;
  • 12월: 일단 회사일이 엄청 재밌어졌습니다. 포켓몬 BDSP + 포켓몬 LA를 사서 합쳐서 90시간을 태웠습니다. 
    • 한바탕 노니까 다시 공부할 Motivation도 생겨서 지금도 그렇고 1월에도 그렇고 다시 열심히 공부할 것 같습니다

 

Sports & Fun

  • 리듬게임 이야기
    • 츄니즘은 결국 아예 접었습니다. 어떻게 된 게 대규모 업데이트가 (CHUNITHM NEW) 나왔는데 새로 나온 곡들 순회조차 안하고 접었는지는 모르겠는데, 어쨌든 접었습니다. 옛날에는 이거하는 것만을 목적으로 일본까지 가고 그랬는데 참 신기합니다. 어쨌든 츄니즘 ㅂㅂ
    • 사볼도 제가 봤을때는 사실상 접었습니다. 비즈니스하는 사람들 골프치듯이 사볼하는 거 외에는 (ㅋㅋ) 안할 것 같아요. 점수 올릴 생각하고 사볼하러 간 다음에 기분만 망친 상태로 집으로 가는 경우가 너무 많아졌습니다. 여기서 더 올라가려면 뇌를 켜야하는데 제가 그걸 잘 못합니다. 
    • 그래서 리듬게임은 아예 접은 것 같아요. 21년 말 ~ 22년 중순까지 덕분에 잘 놀았습니다. 
  • 스포츠 이야기 1 - LoL: T1 응원을 나름 열심히 했습니다.
    • 스프링은 뭐 매우 좋았고 이때는 진짜 T1 경기는 다 챙겨봤습니다. 롤갤에 상주했어요
    • MSI 보러 지인들과 부산에 갔습니다. G2전은 참 좋았는데 RNG전에서 멘탈 나갔습니다. 
    • 서머때는 뭔가 상태가 메롱이라는 말을 들어서 거의 안봤습니다. 결승전은 지인들과 같이 모여서 트위치로 보긴 했는데 ㅋㅋ
    • 롤드컵때는 경기 다 챙겨봤습니다. 이러면 안되는데 인생을 여기에 갈아넣었어요.
    • 대충 8강전 - 일주일 내내 무한리딸 - 4강전 - 일주일 내내 무한리딸을 했고 4강전은 지인들과 롤파크에서 봤습니다. 
    • 결승전을 해외에서 CODEGATE 치러 온 지인하고 같이 CGV에서 봤습니다.
      • 4세트 끝나고 DRX 우승 느낌이 들기 시작하더니 베릴이 바드를 뽑는 걸 보고 DRX 우승이 눈에 보이더라구요
      • 아쉽기는 한데 DRX도 워낙 스토리가 있고 데프트/베릴 둘 다 호감이라 그나마 다행입니다. 역체{봇/폿} ㅊㅊㅊ
    • 페이커가 3년 재계약을 했는데 저는 3년 뒤에도 학부생입니다. 감동적이네요...
    • 내년에 롤드컵이 서울이라는데 내년 10월에 또 롤드컵에 인생을 갈아넣는 게 확정이라 벌써 무섭습니다. 
  • 스포츠 이야기 2 - 미국 스포츠
    • NBA 이야기
      • 일단 21년 파이널이 Suns vs Bucks가 되면서 (둘 다 호감) 진짜 싱글벙글 기분좋게 봤는데 Bucks가 우승을 함.
      • 그래서 22년에 Suns가 좀 잘하면 좋겠다 싶어서 봤는데 2라운드 7차전에서 진짜 대가리가 깨져버리더라구요 ㅋㅋ;
      • 근데 대가리를 깬 Mavericks도 호감이어서 (11년 파이널 + 노비츠키 + 돈치치 등) 좀 잘했으면 좋겠다 싶었는데 상대가 골스임
      • 그래서 파이널 매치업을 보니까 어떻게 된 게 Warriors vs Celtics 여서 이성을 잃었습니다.
      • 확실히 커리가 잘하긴 하는듯요 파엠빼고 다 가졌던 사람인데 파엠을 가져가서 이제 뭐라 못할듯. 물론 지금 골스는 뭐하는지 모르겠습니다.
      • 23년에 대한 희망사항은 요키치와 덴버가 플레이오프에서 좀 잘나갔으면 좋겠습니다. 요키치 매우 호감임.
    • NFL 이야기
      • 사실 22년 플레이오프를 제대로 follow-up을 못했어요. 23년은 조금 더 follow-up을 제대로 해야겠습니다.
      • 슈퍼볼 매치업이 Bengals vs Rams여서 이때는 진짜 아무나 우승해라 마인드였습니다. 둘 다 개고생한 팀이다보니...
      • 대충 AFC 강팀이 Bills/Chiefs/Bengals/Ravens가 있는데 Bills/Bengals 중 한 명이 올라가면 좋을 것 같습니다. 
      • 대충 NFC 강팀이 Eagles/Cowboys/Vikings/49ers 정도 같네요. Eagles/Vikings 중 한 명이 올라가면 좋을 것 같습니다.
      • Seahawks QB였던 Russell Wilson이 트레이드되고 덴버로 가서 개못하고 있는데 복잡한 감정이 듭니다
    • NHL 이야기
      • 22년 플레이오프를 제대로 follow-up을 못했어요. 23년에는 조금 더 follow-up을 해야겠습니다. 22년을 다시보면
        • 토론토가 또 7꽉하고 1라딱 (2018, 2019, "2020", 2021, 2022 5연타)
        • 플로리다가 정규시즌 1위하고 1라를 겨우 통과한 후 2라 스윕딱 ㅠㅠ
      • 토론토가 1라딱하는 거 웃기긴 한데 23년에는 안했으면 좋겠습니다. 얘들 정규시즌에는 개잘하는데 너무 아쉬워요.
      • 4월 중순에 플레이오프 시작인데 이때 토론토로 가서 직관하는 거 진지하게 고려하고 있습니다. 최소한 경기 다 라이브로 챙겨볼듯.
  • 스포츠 이야기 여담: 저는 포르투칼 전을 안보고 잤습니다. 대신 월드컵 결승은 다 라이브로 봤어요. 다행입니다. 

 

+ 2023년에 슬슬 유학 준비를 (GRE 등) 해야할 것 같다는 생각이 드네요

 

쓰다보니 이게 인생 회고인지 스포츠 칼럼인지 모르겠는 걸 보니까 인생이 벌써 크게 뒤틀린 것 같습니다

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

Recent Updates  (4) 2022.08.12
근황 보고  (4) 2022.05.18
6월 및 7월 초 정리  (4) 2021.07.15
4-5월 정리  (1) 2021.05.31
3월 정리  (0) 2021.04.02

https://infossm.github.io/blog/2022/12/05/BLSBNMaster/

 

Optimal Ate Pairings, BLS12-381, BN254 알아보기

이전 글에서 이어서 가겠습니다. Optimal Ate Pairings [Ver09]의 내용입니다. 다시 Tate Pairing으로 돌아가서, \[(f_{s, P}) = s(P) - ([s]P) - (s-1) \mathcal{O}\] 인 함수 $f_{s, P}$를 생각하면, reduced Tate Pairing \[t_r(P, Q)

infossm.github.io

 

'Cryptography' 카테고리의 다른 글

Elliptic Curve Pairings  (0) 2022.11.25
New Lookup Argument  (0) 2022.11.04
Sum-Check Protocol and Applications  (0) 2022.10.24
Polynomial Commitment Scheme from DARK  (0) 2022.10.14
ZK Hash Functions: Design & Analysis  (0) 2022.09.21

https://twitter.com/RareSkills_io/status/1600279157942161408

 

트위터에서 즐기는 RareSkills

“1/ RareSkills is proud to present a totally new way to allowlist addresses for presales and airdrops. The gas efficiency soundly beats ECDSA signatures and Merkle Trees. The method is to use old fashion RSA signatures, but with a lot of tricks. Links an

twitter.com

https://twitter.com/rkm0959/status/1600312617310253056

 

트위터에서 즐기는 rkm0959

“If I'm not mistaken, the contract is vulnerable as you can create signatures for a lot of addresses. This is why cryptography is hard, and needs a lot of attention.”

twitter.com

 

https://infossm.github.io/blog/2022/11/22/PairingMaster/

 

Pairing 제대로 알아보기

자료: Pairings For Beginners Introduction 이 글에서는 여러 암호학의 분야에서 자주 등장하는 Elliptic Curve Pairing에 대해서 자세하게 알아보겠습니다. 독자 대상은 현대대수학 기본 Elliptic Curve 연산에 대

infossm.github.io

 

'Cryptography' 카테고리의 다른 글

Optimal Ate Pairing, BLS12-381, BN254  (0) 2022.12.21
New Lookup Argument  (0) 2022.11.04
Sum-Check Protocol and Applications  (0) 2022.10.24
Polynomial Commitment Scheme from DARK  (0) 2022.10.14
ZK Hash Functions: Design & Analysis  (0) 2022.09.21

 

BlackHat MEA에서 2등했습니다. 인당 40000 SAR ~ $10500 정도 가져가게 될 것 같습니다.

'CTF' 카테고리의 다른 글

CODEGATE 2022 Finals: Look It Up  (0) 2022.11.09
0CTF 2022 ezRSA+++  (0) 2022.09.19
0CTF 2022 TCTF NFT Market  (0) 2022.09.19
WACon 2022 Quals: RSA Secret Sharing  (0) 2022.06.27
CODEGATE 2022 Preliminary : Prime-Generator  (0) 2022.02.28

미러에서 풀었어야 했는데 괜히 능지 더 쓰려다가 못 풀었다. 3시간 째 실제 대회에서 푼 사람이 안 나오길래 엄청 어려운 줄... 

그래도 문자열 문제 어떻게 푸는지 기억이 아예 사라진 것은 아니어서 조금 신기했다. 가뭄에 콩 나듯 하는 PS....

 

Suffix Array + LCP를 만들자. 여기서 만약에 $$\max(lcp_{i-1}, lcp_{j+1}) < \min(lcp_i, lcp_{i+1}, \cdots, lcp_j)$$가 성립한다면, $i-1$번째 substring 부터 $j$번째 substring까지 총 $j-i+2$개의 substring이 $$\min(lcp_i, lcp_{i+1}, \cdots, lcp_j)$$ 길이의 common prefix를 가지며, 특히 $$[\max(lcp_{i-1}, lcp_{j+1}) + 1, \min(lcp_i, lcp_{i+1}, \cdots, lcp_j)]$$ 구간에 속하는 길이의 prefix 들은 정확히 $j-i+2$번 등장하게 된다. 즉, 이들은 $f(j-i+2)$에 들어가는 후보군이라고 볼 수 있다. 

 

그래서 일단 저런 경우들을 모두 관리해야 하는데, 이건 stack을 써서 할 수 있다. 대충 $st$번째 문자열부터 $en$번째 문자열까지 common prefix가 $l$이라는 것을 하나의 struct로, 즉 $(st, en, l)$ 형태로 관리한다고 치자. 그러면 $lcp_i$를 보면서 얻는 것은 $(i-1, i, lcp_i)$라는 struct다.

 

이제 stack을 머리속으로 그리면서 생각을 해보자. 스택의 top을 $S$라고 생각을 하고, 지금 $(i-1, i, lcp_i)$를 본다고 하자.

  • $S_l > lcp_i$인 경우를 생각해보면, 현재 [$S$ 이전의 원소인 $T$], [$S$], [$(i-1, i, lcp_i)$]가 순서대로 stack에 대기중이다.
    • stack 상 invariant를 하나 유지하자. 이제부터 stack에 쌓인 순서대로 $l$ 값이 증가하도록 한다. 자연스러운 생각이다.
    • 그러면 $S_l > \max(T_l, lcp_i)$이므로, 여기서 $f$ 값을 update 할 케이스가 발생한다. 
    • 즉, $[\max(T_l, lcp_i) + 1, S_l]$ 구간에 속하는 prefix들은 정확히 $S_{en} - S_{st} + 1$번 등장하게 된다. 
    • 이제 $f$를 계산하려면 disjoint occurrence 횟수를 계산해야 한다. 
      • 이는 $S$에 대응되는 suffix array 값들을 set으로 관리하고, naive 하게 lower bound를 사용하면서 계산하면 된다.
      • 결국 "최대 occurrence를 유지하는 최대 길이"를 계산해야 하는데, 이는 $[\max(T_l, lcp_i) + 1, S_l]$에서 이분탐색을 하면 된다.
    • 이제 다시 $T_l \ge lcp_i$인 경우와 $T_l < lcp_i$인 경우로 나뉘게 된다. 
    • $T_l \ge lcp_i$인 경우를 생각해보면, 이제 $S_l = T_l$인 것으로 생각해도 무방하다는 것을 알 수 있다.
      • 그러므로, $S_l \leftarrow T_l$로 $S$를 바꾸고, $S$와 $T$를 하나로 합친다.
      • 여기서 합친다는 것은, $(T_{st}, S_{en}, S_l = T_l)$을 만든다는 것이다. 
      • 만약 여전히 $T_l > lcp_i$이면 다시 맨 처음부터 반복하면 된다.
      • 앞서 확인했듯이 $(st, en, l)$에 대응되는 suffix array 값들의 집합을 set으로 관리해야 한다. 
        • 이는 $S$에 대응되는 집합과 $T$에 대응되는 집합을 합치는 것과 같다. 그러니 small-to-large 하면 ok.
    • $T_l < lcp_i$인 경우, 이제 $S_l < lcp_i$인 경우와 같은 방식으로 대응하면 된다. 
  • $S_l = lcp_i$인 경우, 단순히 $S \leftarrow (S_{st}, i = S_{en} + 1, S_l)$으로 바꾸고 set을 관리하면 된다.
  • $S_l < lcp_i$인 경우, stack에 $(i-1, i, lcp_i)$를 push 하면 된다. 

모든 과정이 끝나면, stack에 원소들이 남을 것이며 $l$이 증가하는 순서일 것이다.

위 과정과 마찬가지로 pop하고 prefix들 handle 하고 스택의 다음 원소와 합치는 과정을 반복하면 답을 모두 구할 수 있다.

 

disjoint occurrence 계산을 naive 하게 할 수 있을 거라고 koosaga가 말해줬는데 안 믿은 게 문제다 ㅠㅠ 

엄청나게 어려운 자료구조를 관리해야 할 거라고 생각해서 망했다. 시간복잡도 증명이 매우 궁금한 문제.

 

꾸베릴과 알대인

 

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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <stack>
#include <set>
using namespace std;
typedef long long int ll;
 
bool debug = false;
int ord[51111], nord[51111], cnt[51111], aux[51111];
int sfx[51111], rev[51111], lcp[51111];
string s;
int ans[51111]; 
int app[51111];
 
struct L {
    int len_com;
    int st; int en; int idx;
    L(int len_com, int st, int en, int idx): len_com(len_com), st(st), en(en), idx(idx) {}
};
 
int iidx = 0;
set<ll> VALUES[51111];
stack<L> stk;
 
void SFSA(string str) {
    int n = str.length();
    int p = 1;
    memset(ord, 0sizeof(ord));
    for(int i=0; i<n; i++){
        sfx[i] = i;
        ord[i] = str[i];
    }
    int pnt = 1;
    while(1) {
        memset(cnt, 0sizeof(cnt));
        for(int i=0; i<n; i++) cnt[ord[min(i+p, n)]]++;
        for(int i=1; i<=|| i<=255; i++) cnt[i] += cnt[i-1];
        for(int i=n-1; i>=0; i--)
        aux[--cnt[ord[min(i+p, n)]]] = i;
        memset(cnt, 0sizeof(cnt));
        for(int i=0; i<n; i++) cnt[ord[i]]++;
        for(int i=1; i<=|| i<=255; i++) cnt[i] += cnt[i-1];
        for(int i=n-1; i>=0; i--)
        sfx[--cnt[ord[aux[i]]]] = aux[i];
        if(pnt == n) break;
        pnt = 1;
        nord[sfx[0]] = 1;
        for(int i=1; i<n; i++){
            if(ord[sfx[i-1]] != ord[sfx[i]] || ord[sfx[i-1+ p] != ord[sfx[i] + p]){
            pnt++;
        }
        nord[sfx[i]] = pnt;
        }
        memcpy(ord, nord, sizeof(int* n);
        p *= 2;
    }
    for(int i=0; i<n; i++) rev[sfx[i]] = i;
    int h = 0;
    for(int i=0; i<n; i++){
        if(rev[i]){
            int prv = sfx[rev[i] - 1];
            while(str[prv + h] == str[i + h]) h++;
            lcp[rev[i]] = h;
        }
        h = max(h-10);
    }
}
 
int get_count(int idx, int jump) {
    int ret = 0;
    auto it = VALUES[idx].begin();
    while(it != VALUES[idx].end()) {
        ret += 1;
        it = VALUES[idx].lower_bound((*it) + jump);
    }
    return ret;
}
 
void printL(L S) {
    cout << "len_com: " << S.len_com << endl;
    cout << "st: " << S.st << endl;
    cout << "en: " << S.en << endl;
    cout << "idx: " << S.idx << endl;
}
 
void finish_handle(int upper_cut, L S) {
    if(S.len_com == 0return;
    if(debug) {
        cout << "finish_handle " << upper_cut << endl;
        printL(S);
    }
    int num_times = S.en - S.st + 1;
    int num_app = get_count(S.idx, upper_cut);
    if(num_app < app[num_times]) return;
    int l = upper_cut;
    int r = S.len_com;
    int best = upper_cut, mid;
    while(l <= r) {
        mid = (l + r) / 2;
        if(get_count(S.idx, mid) == num_app) {
            best = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    if(debug) {
        cout << "num_times: " << num_times << endl;
        cout << "num_app: " << num_app << endl;
        cout << "best: " << best << endl;
    }
    if(num_app > app[num_times]) {
        app[num_times] = num_app;
        ans[num_times] = best;
    }
    else if(num_app == app[num_times]) {
        ans[num_times] = max(ans[num_times], best);
    }
}
 
L merge(L S1, L S2) {
    int from, to;
    if(VALUES[S1.idx].size() < VALUES[S2.idx].size()) {
        from = S1.idx; to = S2.idx;
    }
    else {
        from = S2.idx; to = S1.idx;
    }
    int new_st = min(S1.st, S2.st);
    int new_en = max(S1.en, S2.en);
    int new_len = min(S1.len_com, S2.len_com);
    int new_idx = to;
    for(auto it = VALUES[from].begin() ; it != VALUES[from].end() ; it++) {
        VALUES[to].insert((*it));
    }
    return L(new_len, new_st, new_en, new_idx);
}
 
int main(void) {
    cin >> s; SFSA(s);
    ans[1= s.length();
    for(int i = 1 ; i < s.length() ; i++) {
        if(debug) cout << "on " << i << endl;
        while(!stk.empty() && lcp[i] < stk.top().len_com) {
            L S = stk.top(); stk.pop();
            int upper_cut = 0;
            if(stk.empty() || stk.top().len_com < lcp[i]) {
                upper_cut = lcp[i] + 1;
                finish_handle(upper_cut, S);
                stk.push(L(lcp[i], S.st, S.en, S.idx));
            }
            else {
                upper_cut = stk.top().len_com + 1;
                finish_handle(upper_cut, S);
                L S2 = stk.top(); stk.pop();
                L TT = merge(S2, S);
                stk.push(TT);
 
            }
        }
            
        if(stk.empty() || lcp[i] > stk.top().len_com) {
            iidx++;
            VALUES[iidx].insert(sfx[i-1]); VALUES[iidx].insert(sfx[i]);
            L Lv = L(lcp[i], i - 1, i, iidx);
            stk.push(Lv); continue;
        }
 
        if(!stk.empty() && stk.top().len_com == lcp[i]) {
            VALUES[stk.top().idx].insert(sfx[i]);
            L stk_top = stk.top(); stk.pop();
            stk.push(L(stk_top.len_com, stk_top.st, i, stk_top.idx));
        } 
    }
 
    while(!stk.empty()) {
        L S = stk.top(); stk.pop();
        int upper_cut = 1;
        if(!stk.empty()) { upper_cut = max(upper_cut, stk.top().len_com + 1); }
        finish_handle(upper_cut, S);
        if(!stk.empty()) {
            L S2 = stk.top(); stk.pop();
            L TT = merge(S2, S);
            stk.push(TT);
        }
    }
 
    for(int i = 1 ; i <= s.length() ; i++cout << ans[i] << " ";
    cout << endlreturn 0;    
}
 
cs

 

 

'PS > Problem Solving' 카테고리의 다른 글

10, 11월의 PS 일지 - Part 1  (0) 2020.11.08
8월의 PS 일지 - Part 6  (0) 2020.08.31
8월의 PS 일지 - Part 4  (0) 2020.08.12
8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 2  (0) 2020.08.04

https://blog.audit.haechi.io/dfx_finance_attack_overview

 

Haechi Audit Tech Blog_DFX Finance Attack Overview

DFX Finance Attack Overview | Hacking

blog.audit.haechi.io

 

Overall, a very simple attack both in its core vulnerability and the difficulty to analyze the situation.

https://zkresear.ch/t/codegate-ctf-2022-look-it-up-writeup-deeper-look-at-plookup/47

 

CODEGATE CTF 2022: Look It Up Writeup | Deeper Look at PLOOKUP

Introduction On November 7th to 8th, the annual cybersecurity conference called CODEGATE was held in South Korea. Alongside with, a 24 hour CTF was held, where the world’s top cybersecurity researchers solved various challenges on pwn, reverse engineerin

zkresear.ch

 

'CTF' 카테고리의 다른 글

BlackHat MEA Finals  (0) 2022.11.21
0CTF 2022 ezRSA+++  (0) 2022.09.19
0CTF 2022 TCTF NFT Market  (0) 2022.09.19
WACon 2022 Quals: RSA Secret Sharing  (0) 2022.06.27
CODEGATE 2022 Preliminary : Prime-Generator  (0) 2022.02.28