rkm0959

학교 : 1학기를 4.25/4.3으로 마무리했다. 전기전자회로에서 실수를 해서 A0가 떴고, 나머지는 A+.

돌아보면 그래도 실해석학과 복소1이 가장 재밌었다. 딥러닝은 아직도 잘 모르겠다... 시험은 그냥 수학이었고...

군대/회사 : 회사에 들어왔다. 자세한 사항은 아마 병특 확정이 되면 여기에도 쓸 수 있을 것 같다.

회사에 들어왔으니, 여기서 다양한 일을 하면서 많이 공부를 하고 싶다. 돈도 돈이지만 경험도 중요하니까..

정보처리산업기사 실기를 봤다. 이거 준비한다고 시간을 또 은근 썼는데, 지금 보면 아깝기도 하고 ㅋㅋㅋ

연구 : 공부는 계속 재밌고, 연구 주제는 계속 바뀌고 있는데 곧 "진짜" 확정이 될 것 같다..

연구 주제 외의 최적화 분야 공부는 소멤 글로 정기적으로 올라갈 것 같다. 재밌는 내용이 많다 확실히...

CTF : 당장 이번 주말이 구글 CTF고, 상당히 이를 악물고 참가할 계획이다. 팀 모두가 열심히 하면 좋겠다.

그거랑 별개로 최근에 0CTF에서 zer0lfsr+를 해결한 건 오래 기억에 남을 것 같다. 오래 고민해서 문제 푼 거 되게 오랜만임.

회사를 다니기 시작하면서 정말 시간을 아껴 사용해야 함을 느낀다.

또 더욱 많은 사람을 만나기 시작하면서 세상에는 대단한 사람이 많음을 느낀다.

열심히 해야지,, 그렇다고 노는 걸 아예 포기하기는 그렇고, "출퇴근 시간에서 모든 여가활동을 할 수 있게" 컨텐츠를 바꿀 생각.

이건 아마 한동안 오락실을 (츄니즘) 가지 못할 것 같다는 의미기도 하다. 사실 최근에 코로나가 하도 빡세진 것도 있고, 오락실을 가도 별로 성과가 나오는 것도 아니어서 오히려 잘 됐다. 어쨌든 시간을 잘 쓰는 것을 연습해야겠다... 은근 버리고 있는 시간이 많은 것 같다. 잠도 조금 줄이고,,

This writeup is a compilation of my thoughts and discussions with others.

My solutions are at https://github.com/rkm0959/Cryptography_Writeups/tree/main/2021/0ctfquals.

Problem 1 : zer0lfsr- (35 solves)

Introduction

There are three LFSR/NFSR based keystream generators. We are given

• first 40000 bits of the keystream
• SHA256 hash value of the key

We need to find the key for each generators, but actually we only need to do 2 out of 3. 

Note that the three problems are completely independent in this challenge. We will do #1, #3.

Solution for Generator3

Generator3 is a good target because it doesn't have any NFSR parts. However, it does have a "filter function" $f$. 

There are two methods to get around this filter function $f$, both which can be derived from classic approaches.

NOTE : Read https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/boolean_function.html

The first method computes the algebraic immunity of $f$. Sagemath gives us that $f$ has algebraic immunity of $2$, which means that there exists a polynomial $g$ of degree $2$ such that $fg = 0$ for all inputs. If $f = 1$, which we can directly verify using the output bit, we can immediately recover $g = 0$. Since $g$ has degree $2$ and every LFSR bit is a linear combination of the initial 64 bit key, each information $g = 0$ gives us a linear equation on $\displaystyle 64 + \binom{64}{2}$ monomials of degree no more than $2$. Note that $x^2 = x$ on $\mathbb{F}_2$. Since we have 40000 bits of keystream, we will get about 20000 linear equations. We can now solve the system of linear equation, and recover the 64 bit key as desired.  

The second method notes that for $$f_3(x_0, x_1, x_2, x_3, x_4, x_5, x_6) = x_1 + x_6 + x_0 x_1 x_2 x_3 x_4 x_5 + x_0 x_1 x_2 x_4 x_6$$ we have the incredibly precise linear approximation of $$\overline{f}_3(x_0, x_1, x_2, x_3, x_4, x_5, x_6) = x_1 + x_6$$ which matches $f_3$ for a ton of inputs, I believe $31/32$ of them.

This implies that we have a alternate keystream that directly follows the LFSR recurrence and matches the actual keystream quite well. This alternate keystream can now be found by fast correlation attack. The real key can be quickly derived from the alternate keystream. 

NOTE : Read https://iacr.org/archive/fse2011/67330055/67330055.pdf for the fast correlation attack.

I used the first method for solving this part, as I was not (and still not) familiar with the fast correlation attack.

Solution for Generator1

I chose Generator1 as a good target, because we can bruteforce all $16$ bits of the LFSR part of the key.

If we do this, we can derive all LFSR results by direct calculation. We now need to recover the NFSR part. 

The key idea here is that the function $h_1$, which is $$h_1(x_0, x_1, x_2, x_3, x_4) = x_1 + x_3 + x_0 x_3 + x_0 x_1 x_2 + x_0 x_2 x_3 + x_0 x_2 x_4 + x_0 x_1 x_2 x_4$$ has a close function independent of $x_4$, which is $$\overline{h}_1(x_0, x_1, x_2, x_3) = x_1 + x_3 + x_0 x_3 + x_0 x_1 x_2 + x_0 x_2 x_3$$ This matches $h_1$ for $15/16$ of the input. If we look at how the function $h$ is calculated, it takes the first four bits from the LFSR and the last bit from NFSR. The problem is that we don't really know much about the NFSR. However, we can now use $\overline{h}_1$ and the four bits from LFSR. 

This implies, after bruteforcing the 16 bits of the LFSR, we can calculate all $h$ values, each with probability $15/16$. Since we know the output bits $f$, which is the XOR of the first bit of NFSR and $h$, this means we can recover each NFSR bit with probability $15/16$.

We do this $48$ times to find all NFSR bits. The success probability is around 4%, which is pretty decent. This solves Problem 1.

Problem 2 : zer0lfsr+ (2 solves)

Introduction

The three Generators are identical to the first problem. The major differences here is 

• We now have the "majority" of the three output bits from each generators. 
• We now have 160000 bits, but we don't have the SHA256 hash of each key.
• The three keys are related by the "KDF" function, i.e. $key_2 = KDF(key_1)$, $key_3 = KDF(key_2)$.
• We have to find all three keys in 100 seconds to solve the problem.

Of course, the majority function has a 75% correlation with each generator's output bits. 

If we know one generator keystream, we can guarantee about 25% of the other generator keystream bits.

If we know two generator keystreams, we can guarantee about 50% of the other generator keystream bits.

A look at the KDF

After having a miserable day with this challenge, barkingdog noted an important property of the KDF function. 

His intuition was that the KDF function was way too complicated for it to be a "random function". Indeed, if we just wanted a random output, we can just return some bits of the SHA256 hash. Also, he noted that the repeated values in the round key and subkeys are suspicious.

These suspicions are indeed valid, as there is a important result on this KDF.

Claim : Let $K = K_0 || K_1 || K_2 || K_3$. Assume we know $KDF(K)$.

If we know one value out of $K_0 \oplus K_1$ and $K_2 \oplus K_3$, we can calculate the other value very fast. 

To explain this, note that the two round keys in the middle are the same, which means we can recover the XOR value of the two subkeys from $KDF(K)$. The two subkeys are some reversible and bijective transformations applied on $K_0 \oplus K_1$ and $K_2 \oplus K_3$.

This gives a straightforward method to accomplish our objective of the Claim. This result is very strong, and used heavily in my solution. 

Let's think about the order in which we are going to solve the problem. 

• If we start from Generator1 and succeed in finding $key_1$, we can just use KDF function to directly finish.
• If we start from Generator3 and succeed in finding $key_3$, we can use the KDF property to make solving Generator2 easier.

Of course, analyzing Generator1 with just 75% correlation seems very difficult, so we have to start from Generator3. 

Therefore, the natural idea is to go from 3 to 2 to 1, utilizing known keys and the KDF property to make things easier each step. 

Solution for Generator3

The fast correlation attack solution works here, since we still have nearly 75% correlation to a simple LFSR.

I had some time trying to make this solution stable, as the attack is probabilistic. I ended up doing

• Find 64 bits that have highest probability of being correct, and assume at most one is incorrect.
• We compute all possible values for $key_3$, and calculate the Generator3 keystream.
• If it matches at least 7000 out of the first 10000 given output bits, then we found the key.

Honestly, I'm definitely not the person to ask how to write a reliable fast correlation attack :(

My attack for Generator3 succeeded in about 50% probabilty, and it worked in 8 seconds.

Solution for Generator2

From solving Generator3, we have some additional information at our hands, i.e.

• We know around 40000 bits of the Generator1 output, and the same for Generator2.
• We know $key_3 = KDF(key_2)$, so we can use the KDF property, giving easy 16 bits of information.

To solve Generator2, we need two properties of $f_2$ and $h_2$. First, note that $$h_2(x_0, x_1, x_2, x_3, x_4, x_5, x_6) = x_0 x_1x_2 x_3 x_4 x_5 + x_0 x_1 x_2 x_4 x_6 + x_1 x_3 x_4$$ is $0$ for $7/8$ of the inputs. Therefore, we can ignore the $h$ part of the clock output with high probability. Also, we note that $$f_2(x_0, x_1, x_2, x_3, x_4, x_5)$$ which is a very long polynomial defined by array f_OUT, has a linear approximation $$\overline{f}_2 (x_0, x_1, x_2, x_3, x_4, x_5) = x_1 + x_2 + x_5$$ which matches $f_2$ with a $3/4$ probability. This can be found by calculating the nonlinearity of $f_2$. 

Therefore, the output of Generator2 is close (matches with significantly higher probability than 0.5) to a keystream generated by a LFSR with the same recurrence. If we find this LFSR keystream, we can find the LFSR part of the $key_2$. The NFSR part of the $key_2$ can be directly derived by the KDF property. To find this LFSR keystream, we use yet another fast correlation attack. To be exact, I did

• I only considered the approximately 40000 guaranteed Generator2 bits.
• I found 32 bits that have the highest probability of being correct, and assumed at most one is incorrect.
• Now we have around $32 \times 2^{16}$ possibilities for the LFSR part of the key.
• Here, the $32$ part comes from assuming one bit is incorrect.
• The $2^{16}$ part comes because the LFSR part is 48 bits, and we know 32 bits of the LFSR output.
• If we know LFSR part of the key, the NFSR part of the key can be computed by the KDF property. 
• For each possible key, we compute the KDF and see if it matches $key_3$. 

My attack for Generator2 succeeded in about 25% probability, and it worked in 20 seconds.

Solution for Generator1

From solving Generator2, we have some additional information at our hands, i.e.

• We know around 80000 bits of the Generator1 output.
• We know $key_2 = KDF(key_1)$, so we can use the KDF property, giving easy 16 bits of information.

Here's a rough idea. If we bruteforce LFSR part, using the same ideas as Problem 1, we can get 24 bits of the NFSR part. Also, we have the 16 bits of information from the KDF property. This adds up to 40 bits of extra information. Therefore, intuitively, we can find about $2^{24}$ candidates for the first key. After that, we can test each of them by either calculating the KDF or calculating the Generator1 output, and testing if it matches the guaranteed Generator1 bits. To be more detailed, I did as follows : 

• I bruteforced the 16 bit LFSR part, and this gives approximately 24 bits of NFSR information
• This means we have full $K_3$ and around 8 bits of each of $K_0, K_1, K_2$. 
• We bruteforce the undecided bits of $K_2$. Now we know $K_2 \oplus K_3$, so $K_0 \oplus K_1$ as well.
• We know around 16 bits of $K_0, K_1$ in total, and we know $K_0 \oplus K_1$.
• This is enough to get a small number of candidates for $K_0, K_1$. 
• In total, this is around $2^{24}$ level of bruteforce to find all candiates. 

I did this in C++ with 10 cores. I checked the validity of each key by testing if the Generator1 output matches the guranteed bits. 

My attack for Generator3 succeeded in about 20% probability because the code had to run in time. I set a timeout of 60 seconds.

Overall, my code found the 3 keys in about 25 trials, but I made a dumb programming mistake, forcing me to fix and try again.

The next time, the code found the 3 keys in about 90 trials, and I got the flag. I think the code works in about 2~3% probability.

Problem 3 : zer0lfsr++ (1 solve)

Introduction

The change from lfsr+ to lfsr++ is

• The three keys are independent of each other, so no KDF property to exploit.
• We can ask for the first 16 bits of one of the three keys.
• We have more time, 180 seconds instead of 100 seconds

It's clear that Generator3 can be solved in the exact same way. The problem is Generator2 and Generator1.

Solutions and Thoughts

Assume we use the hint on Generator2. Then we can get the NFSR part of the key. 

Therefore, it's clear that the solution from Problem 2 works in this challenge as well. 

Of course, we need to check the validity of the key differently (instead of using KDF) but this is not hard. 

We can just check if the Generator2 output matches the guaranteed Generator2 bits. 

If we use the hint on Generator2, we have nothing to use on Generator1, other than around 80000 bits of Generator1 guranteed.

This can be solved in two ways, as shown by the author and the only solver hellman : 

• The author used the methods in https://www.iacr.org/cryptodb/archive/2006/FSE/3235/3235.pdf.
• hellman used z3 to recover the first key. z3 is indeed very powerful...

I thought about using the hint on Generator1 (which makes solving Generator1 relatively the same) and optimizing the fast correlation attack for Generator2, making it more reliable. For example, if I could find 48 bits that I can guarantee with high probability, allowing at most one mistake, I would be able to solve the problem. I was able to get 43 out of 44 bits correct, giving a complexity of around $44 \cdot 2^{20}$, which may be feasible. However, according to the author, the NFSR part of the key may not be uniquely determined. Therefore, this approach leads to a solution that is both slow (but probably within time limit with sufficient computational power) and has low success rate.

I was tired staying up all night solving lfsr+ and I didn't have a lot of time, so I did not implement my approach. 

Looking back, if I had just decided to use z3 on Generator1, I think I would've solved it. I need to practice using z3...

This is an extremely rough sketch.

Problem 1 : zer0lfsr-

• only need to solve 2 out of 3 generators

Generator1

• h can be calculated without the last input with high probability
• bruteforce LFSR 16 bits, then directly recover NFSR 48 bits with 48 output bits

Generator2

• h is zero with high probability
• f has nonlinearity 16, so f is equal to a linear function with 3/4 probability
• therefore, a fast correlation attack can be used

Generator3

• f is very close to a linear function, so a fast correlation attack can be used
• f has a degree 2 annhilator, so we can use this as well to solve the problem

I solved Generator1 and Generator3 with annhilators.

Problem 2 : zer0lfsr+

We solve from Generator3 to Generator2 to Generator1. 

• An important note in the KDF function (found by barkingdog)
• If we know $KDF(K_0 || K_1 || K_2 || K_3)$ and $K_0 \oplus K_1$, then we know $K_2 \oplus K_3$
• we also have a symmetry, if we know $K_2 \oplus K_3$ then we know $K_0 \oplus K_1$

Also, note that the output value is the majority of the three outputs, so we have 75% correlation.

Generator3 can be solved by a fast correlation attack, similar to Problem 1. This works around 50% of the time.

For Generator2, fast correlation attack on bits that we know for sure (i.e. bits where Generator3 and actual output are different, forcing Generator1 and Generator2 to be equal to the actual output) can be used. This is supposed to be used to find all 48 bits of the LFSR, but to do so we need all 48 bits to be perfectly sound, or have very few of them to be incorrect. This is hard to do, so what I did was find 32 bits that we can guarantee its value, assume that at most one of them is wrong. This gives us about $2^{16}$ possibilities for the initial LFSR. Then, we bruteforce all possibilities for LFSR. By the KDF property, we can uniquely recover the NFSR initial state.

This gives us an attack that works around 20 seconds in Python with success probability of around 20%. 

For Generator1, we do something like the following - 

• bruteforce all 16 bits of the LFSR part
• we know about 24 guaranteed bits of the Generator1
• this gives about 24 bits of the NFSR part (by the solution of zer0lfsr-)
• combined with the KDF property, we can get around $2^{24}$ possibilities for the key

For Generator1, I used C++ with multicore programming to fit in time. 

Problem 3 : zer0lfsr++

Generator3 is the same. We will use the 16bit hint on Generator1. This gives us something like

• bruteforce all 16 bits of the LFSR part, and we know first 16 bits of the NFSR part
• we know 8 guaranteed bits out of the first 16 bits of the Generator1 output
• by checking this, around $2^8$ possibilities for the LFSR remain
• out of the 32 remaining NFSR parts, we know 16 of them with the LFSR and the guaranteed Generator1 bits
• so 16 of them remains, and bruteforcing gives us around $2^{24}$ keys

Therefore, we need to do Generator2 without any extra information. To do this,

• A very careful fast correlation attack using all bits (including non-guaranteed bits) can be done
• I was able to find 44 bits that we can guarantee with at most one incorrect bit
• we brute force the remaining 20 bits, so something like $2^{20} \cdot 44$ possibilities, doable

I believe with C++ with multicore programming and some luck, we can definitely solve it with this strategy.

UPD : Apparently there are multiple solutions for Generator2, so we need to use the hint on Generator2.

http://www.secmem.org/blog/2021/06/15/SCLI_Framework_and_Applications/

http://www.secmem.org/blog/2021/04/15/Cataylst_Framework/   

http://www.secmem.org/blog/2021/05/04/VarianceReductionCatalyst/ 

학교 : 여전히 실해석은 재밌다. 중간고사를 봤고 대충 무난하게 끝난 것 같다.

CTF : 4~5월에서는 크게 인상깊은 대회를 하지는 못한 것 같은데, 그래도 재밌는 거 몇 개 배웠다. 소멤으로 쓸 듯.

군대 : 한 회사를 붙어서 아마 산업기능요원 복무를 시도할 것 같다. 정보처리산업기사를 떨어지는 참사가 벌어지지 않는다면, 확정된 것은 아니지만 아마도 여기서 복무를 할 수 있을 것 같다. 어쨌든 1학기 끝나고 회사를 다니는 것은 확정. 자취 여부는 아직 모르지만, 그래도 (산기가 되면) 2022년에는 자취하지 않을까?

연구 : 위 문제로 연구를 급하게 끝낼 이유가 없어져서, 조금 여유를 갖고 천천히 문제를 고민하기로 했다. 길게 재밌게 연구할 수 있는 주제를 찾고 공부하고자 한다. 끌리는 대로 논문 읽는 것도 다시 해야할듯. 일단 지금 받은 주제들도 계속 보고 생각하는 것으로 ㅎㅎㅎ 교수님 정말 친절해서 좋다.

5월 초에 여러 중요한 일을 처리하느라, 5월 말에 되게 집중하지 못했다. 

PS 정수론도 개편한다고 말만 해놓고 하지 못하고, 블로그도 방치했다. 이러면 안되는데 ㅋㅋ...

노는 것도 적당히 놀고, 할 일은 집중해서 잘 처리하는 내 모습으로 빠르게 돌아올 수 있으면 좋겠다. 

600문제는 아마 영원히 못 풀지 않을까?

연구 : 연구 재밌고 분야 공부 자체가 재밌다. 글을 더 쓰고 싶기는 한데 조금 더 두고 봐야

학교 : 실해석이 진짜 어려운데 진짜 재밌다. 딥기는 뭔가 과제와 수업 사이의 차이가 있는 것 같다.

CTF : 이번 달 CTF는 되게 나도 잘했고 팀원들도 잘했다. zer0pts CTF 우승이 제일 기쁜 성과. picoCTF 문제도 냈다.

기타1 : github.com/rkm0959/rkm0959_implements 이거 키우고 싶다 ㅎㅎ;

기타2 : 소멤 자주 가는데 친구도 만나고 좋다. 별개로 새로운 사람을 적당한 선에서 많이 만나려고 노력하고 있다.

기타3 : 27인치 모니터를 샀고 Spotify 가입도 하고 여러모로 돈을 좀 썼는데 소멤으로 커버됨 ㅎㅅㅎ