512bit인 의 128lsb를 마음대로 입력할 수 있고 ciphertext를 골라서 decrypt된 결과의 하위 129번째 bit를 출력해주는 상황이다.
을 입력하면 에 대한 정보를 얻을 수 있다.
즉, 의 한 비트를 얻는 것이고 상에서의 값만 신경쓰면 되기 때문에 이 최대한 작아야 하고, 따라서 의 lsb를 1로 설정해 주었다.
1024bit인 을 128bit인 8개로 표현할 수 있다.
위와 같이 128개의 암호문을 차례로 보내면 129~2번째 비트를 알 수 있다. 여기서 1번째 비트는 0 또는 1 (1/2의 확률)로 무작위로 정해야 한다.
여기까지 하고 꽤 오랜 시간을 고민하다 아이디어가 생각났다.
이라 하면 우리는 의 하위 128bit를 알아내야 한다.
이렇게 설정하면 oracle을 이용하여 의 하위 128bit를 leak할 수 있고 은 이미 아는 값이므로 의 하위 128bit, 즉, 를 leak할 수 있다.
같은 방식으로 나머지 들도 구해주면 온전한 을 구할 수 있다.
v = v ^ (v >> k)
v = (v ^ (v << k)) & ((1 << 256) - 1)
v = v ^ random_value
위의 코드가 랜덤한 순서로 나열된 32개의 함수가 있고 이들은 8bit를 return한다.
이 함수들에 들어가는 인자가 256bit크기의 flag인 상황이다.
중간중간에 v &= 2^256-1
가 있는 것을 보고 상에서의 연산임을 알 수 있었고 xor과 shift연간이 모두 linear함을 알 수 있었다.
따라서 flag를 256개의 변수로 취급하면 32개의 함수에서 8bit를 반환하므로 개의 식을 얻을 수 있다. solve_right하면 끝
대면으로 ctf본선에 처음 참여해 보았다. 네임드 해커들을 실물로 보는 것이 신기했고 대회장 시설이 생각보다 너무 좋았던 것도 신기했다.
전날 과제 이슈로 아침엔 정신을 못 차렸다. 대회장 음악이 생각보다 커서 점심 이후로 에어팟 끼고 제대로 집중하기 시작했고 대회 시작 6시간만에 RSA lsle를, 4시간 뒤에 XOR Disaster을 풀었다. web3문제는 좀 보려다가 지금 체급으론 어림없을 것 같은 강한 느낌이 들어서 빠르게 손절했다.
참가자 리스트를 보고 꼴등만 하지 말자는 마인드로 임했는데 운이 좋게도 8등으로 대회를 마무리했다. 솔직히 상금(50만원)도 타고 10등 안에 들어서 기분이 굉장히 좋았다 😚😚
내 위에 CyKor 형님들 세 분이 각각 포너블, 웹, 크립토 분야 문제를 다 푸신 것을 보고 대단하다고 다시금 느꼈다. (특히 포너블은 대회 종료 10분?즈음 전에 퍼블 내셨는데 미친 끈기인 것 같다..)
크립토가 비교적 솔버가 적어서 2문제를 풀고도 10등 안에 들 수 있었던 것 같다.