Mar 10
This is part 2 of the reverse engineering ippsRSA library to induce faults.
So, it's legitimate from the previous post that I need to fault either of the subkeys s1 and s2 to derive the RSA private key. I was having a binary that used the ippsRSA library to sign a message. (could not share because of license reasons. One could do it by following the reference manual)
Oh okay… where do I start now? Well, I had two start points.
- Statically checking the code flow in Gdb, Ghidra. Then proceed for runtime analysis.
- Going through the Intel® Integrated Performance Primitives Cryptography Developer Reference which had some explanations of the functions that I came across in Ghidra and gdb.
At first, I did some surfing inside binary by jumping into different functions.
On disassembling the main function with some basic common sense, I concluded that I will have to dig into the sign function.
sign function had hell a lot of jump statements and some meaningful functions. The rest of the functions were related to Intel’s proprietary Big Number format. The more relevant one was the “ippsRSA_Decrypt”.
Seems like I am on the right path. No information about where signatures are computed yet. I said to myself…Dig Deeper…
Upon disassembling <ippsRSA_Decrypt> I found that I was nearing a dead-end as the only function being called did not get disassembled throwing error. Also, the developer manual did not hold much information regarding the implementation.
Ah oh… What was I doing all this time? Static Analysis. Now time for some dynamic analysis. I put in some message which was to be signed as input and tried to reach the dead end. Bammmmmmm!! Dead-end now opened its door. Now the ippsRSA Decrypt had almost 6 different functions being called. 1 of them was named more relevant.
m7_gsRSAprv_cipher_crt → this one because it had crt in its name. YUP, my neurons in the brain predicted that crt should stand for the Chinese Remainder Theorem. Now what? do the static analysis first.
Surprise!! this time on static analysis the function had multiple calls to functions that were loaded during run time as well. 5–6 functions were preloaded and they held in them around 2K lines of instructions in the total. And not even the way they were named revealed any information. I could not figure out any trace about the sub-signature part either. Remember, that’s where I was trying to induce a fault.
I figured out that I had around 224 functions that seemed relevant for my Intel processor’s architecture to compute RSA signature. And I was not sure about those run-time-loaded functions too.
At this point, I felt like I was lost. Upon doing runtime analysis also I could not find much information on where the s1 and s2 are being computed. As the functions responsible for multiplication, division, Montgomery, Encode and Decode Montgomery operations were called in multiple places and multiple times, I had to keenly reconstruct the mental model of the code flow.
Ah, hold on. Time for some brute-forcing. I injected some faults in places where these functions were being called. Yeah... I got some faulty signatures, but when I did the gcd calculation, I could not derive the private key. GCD I found was 1, which cannot be the value of prime factor q in RSA anywhere in a milky way. This indicated that I was inducing faults at the wrong places.
At this point, the reference manual did not make any sense to me as I went many layers in depth doing reverse engineering.
Now What??
I had also seen the Github repo of the library sometime back. But was not certainly sure if it will have some information about these low-level functions that appear in gdb or ghidra. Keen eyeballing and a bit of surfing across revealed, this header file could lead me to the points where multiplications happen.
The following code blocks are our region of interests. (Refer to the comments in the image shown below)xq=x^dq mod Q (s1)xp=x^dp mod P (s2)and recombination
So I quickly pulled down the fault injection simulator(was not in the mood to kill my DRAM with Rowhammer during exams ;p)
And injected faults in the following address, where the gs_mont_mul was called. I speculate that this function is responsible to call the Montgomery multiplication for s1. With the fault injection simulator, I used skip instruction to inject fault.(more info on the repo’s readme).
Then I produced clean signatures by doing a normal run and putting it in a file.
The image below contains the corrupted signature produced, after injecting fault in the multiplication operation. Signatures of both the terminal images do not match.
Finally, the Python script helped in recovering the rsa_crt primes p and q. I also had the p and q values, then calculated the same separately from the gcd math as explained in the Bellcore Attack(also in my previous post).
With almost 10 hours put on this, starting from scratch till recovering the P and Q signatures, I was not done. Time for some extra mile drive.
I also found some more locations where injecting faults also provided faulty signatures. Some of them are for your perusal.
Injecting faults at different places where gs_mont_mul called only was able to induce faults at multiple places. Other functions like m7_gsModExpWin_BNU_sscm, gs_mont_red were also getting us the exploit work.
Yay!! you made until the end of my post. You could also try injecting faults in simple binaries, using the simulator to create changes in the control flow of your code.
Above all, Stay Happy!!
P.S: I am quite thankful to Prof. Micheal Schwarz, CISPA Helmholtz Center for Information Security for his amazing lectures and cool puns.
References:
- Onur Mutlu and Jeremie S. Kim. 2020. RowHammer: A Retrospective. Trans. Comp.-Aided Des. Integ. Cir. Sys. 39, 8 (Aug. 2020), 1555–1571. DOI:https://doi.org/10.1109/TCAD.2019.2915318
- https://eprint.iacr.org/2012/553.pdf
- https://github.com/misc0110/FaultInjectionSimulator
