This article primarily introduces how to perform differential cryptanalysis on the traditional block cipher algorithm FEAL-4, and demonstrates the attack process and key implementation details. The text also includes some experimental data and attack results for interested readers to reference or reproduce.
Two Important Images
Before delving into the analysis, here are two images closely related to FEAL-4 to provide an intuitive understanding of differential propagation and the overall encryption process.
Differential Propagation Diagram The figure below shows how plaintext differences (in XOR form) propagate through the encryption rounds in FEAL-4 and ultimately reflect in the ciphertext.
FEAL-4 Workflow Diagram The following figure illustrates the overall encryption framework of FEAL-4, including the left and right blocks of the plaintext, the injection of round subkeys, and the usage flow of the F function.
Characteristics of the F Function
The round function of FEAL-4 (i.e., the F function) can be viewed as some form of random permutation on a 32-bit input. In differential analysis, we do not need the specific implementation of F, but rather focus on its two key differential properties:
If , then .
If , then .
With these two conclusions, we can infer the output behavior under specific differential inputs in subsequent analyses, thereby aiding in locating the subkeys.
Detailed Analysis of Differential Paths
Suppose we choose a pair of special plaintexts and such that: This specific differential vector helps simplify the differential computations in several rounds of FEAL-4 outputs.
1. Derivation of Initial Round Differences
Let denote the left and right blocks of (similarly, denotes those of ).
After the XOR operation in the first round: Similarly, the differential of the right half can be derived.
Furthermore, due to the “additional XOR round” during encryption, we obtain: This implies that in subsequent computations, the differences can be merged in a simpler form.
2. Backward Differential Calculation
After obtaining the plaintext pair and the corresponding ciphertext pair , further backward derivations can be made. Let the ciphertext be denoted as , then:
Compute , obtaining .
Based on the known differential properties, gradually restore intermediate variables such as , , , etc., in the last round.
Using these results, attacks or verifications on the subkeys can be performed.
Attacking K3
In differential analysis, one often starts with attacking an intermediate round subkey, such as . The specific steps are as follows:
Select Plaintext Pairs: I generated 12 pairs of random plaintexts satisfying
Encrypt and Extract Differences: Encrypt the above plaintext pairs to obtain the corresponding ciphertext pairs; combine with the differential path to derive intermediate values , , , etc.
Traverse : Any candidate that satisfies the differential equation is retained.
Using this method, I successfully obtained four candidate subkeys:
1
cfa38976, cfa309f6, 4f238976, 4f2309f6
An example command to execute the above process is:
1
./main -mode=attackk3 -file=K3.txt
This implementation is consistent with the method I introduced on www.theamazingking.com.
Attacking K2
After obtaining several candidates for , we can proceed to deduce . The core equation is: where comes from the previous round operations (including further computations on , , etc.). Similarly:
Generate plaintext pairs that satisfy the differential condition
Capture ciphertext differences after encryption, and by traversing all possible values, check if the differential constraint is satisfied.
Similarly, attacking can be done following the previous process. To ensure the differential path consistently presents the expected results, I generated 12 plaintext pairs satisfying and verified their encryption outputs.
This allows you to input all previously obtained candidate combinations of and at once, and finally find the corresponding candidates.
Attacking K0, K4, K5
Once , , and are all obtained, , , and required for the last round can be deduced. Let the final encrypted left and right parts be , . The corresponding plaintext blocks are , . Then:
By enumerating all possible , the corresponding and can be solved through the above equations. Then, use other plaintext-ciphertext pairs to cross-validate correctness. If all are satisfied, the correct final key set is obtained.
Automatically Generate Random Plaintext Pairs: Control the XOR differences in the code in advance to batch output plaintext files that meet the requirements (e.g., K3_p.txt, K2_p.txt, K1_p.txt).
Parallelized Search: Use Go’s Goroutines to start 10 parallel tasks, maximizing CPU resource utilization on a 10-core Mac.
Progress Bars and Visualization: Use the progressbar library to display search progress in real-time, making the experimental process more intuitive.
2. Verification Methods
Local Custom Key Testing First, select a set of known – (e.g., 0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020), encrypt the previously generated plaintext pairs, and repeat the differential analysis process to see if this set of keys can be matched among the results. Experiments confirmed the ability to correctly restore this set of test keys, thereby verifying the accuracy of the code logic.
Specific Plaintext-Ciphertext Pair Testing Select a plaintext 1234567890abcdef and the ciphertext f43ae3eeb56e2bbf generated in the Einstein Zone, and verify that each of the 256 candidate – sets can reproduce this encryption mapping, further confirming the attack process is correct.
Final Results
All deduced – are stored in final_result.txt. After deduplication, they include the following ranges:
With the aid of differential analysis, we ultimately obtained a set of candidate subkeys. Compared to modern block ciphers (such as AES), FEAL-4 has fewer rounds and a simpler structure, making it very suitable for demonstrating the concept of differential analysis in teaching and research.
Conclusion
This article detailed the complete process of performing a differential attack on FEAL-4, including designing differential paths, generating plaintext pairs, attacking intermediate subkeys (, , ), and finally reverse-solving for , , . It also introduced several optimizations and verification methods during the code implementation process. The FEAL-4 algorithm, due to its fewer rounds and simpler structure, provides convenience for differential analysis. However, for more secure and complex modern block algorithms, the same analytical approach remains crucial. This case study aims to inspire learners and researchers in cryptography. If you have any questions or improvement suggestions, feel free to discuss and exchange ideas in the comments section!
For DCU’s Secure Programming course, the disassembly problems have a certain pattern. Using a fixed approach to solving them can help achieve quick results.
The position of ebp is the saved frame pointer, and ebp+4 is the return address. Since the problems typically assume all parameters are of type int or int*, ebp+8, ebp+c, and ebp+10 correspond to the first, second, and third parameters, respectively.
By quickly scanning the code for occurrences of 0x__(%ebp) and identifying the largest offset, the number of parameters can be determined as (offset - 4) // 4.
Here, 0x10(%ebp) exists, so the parameter count is (16 - 4) / 4 = 3.
We can construct the framework of the code as:
1 2 3
intfoo(int a, int b, int c) {
}
a, b, and c correspond to ebp+8, ebp+c, and ebp+10, respectively. Note that parameters are pushed onto the stack in reverse order, so the closer to ebp, the earlier the parameter appears in the list.
For now, assume all are int types. Adjust later if inconsistencies are found.
Identify the Number of Local Variables
The number of local variables is determined by the third line of the code: sub $0x4, %esp. The amount subtracted corresponds to the length of the allocated local variables.
In this example, sub $0x4, %esp indicates 4 bytes, so there is one local variable. Assume it is an int and name it i.
The code expands to:
1 2 3
intfoo(int a, int b, int c) { int i; }
Recognize the Loop Body
Loops are typically while or for loops. To identify:
Judgment Entry:
Look for a comparison instruction (e.g., cmp) followed by a jump instruction (e.g., jge or jle).
These indicate the start of a condition check.
Loop Body:
Unconditional jmp instructions signify loops. The jump target is the beginning of the condition check.
Condition:
The judgment condition combines the comparison and preceding instructions into a complete condition.
The combination of cmp and jge indicates a judgment entry.
Loop:
The jmp command jumps to <foo+12>, signifying the loop condition check.
Condition:
mov -0x4(%ebp), %eax: Assigns the value of i to eax.
cmp 0x10(%ebp), %eax: Compares eax (value of i) with c.
This calculates i - c and checks the condition with jge. In assembly, conditions are reversed compared to C: jge skips the loop if the condition is met. Thus, the C condition is i - c < 0.
The code updates to:
1 2 3 4 5 6
intfoo(int a, int b, int c) { int i; while (i - c < 0) {
In a previous article, I used Obsidian’s QuickAdd to create a script that automatically converts text copied from ChatGPT and fixes the LaTeX formatting. However, there is no suitable plugin available for the Craft app.
We can use Raycast to achieve this functionality uniformly.
Create a Raycast Script
First, we need to create a script.
Next, select the Bash template.
Then, we edit the Bash script and enter the following code:
# Documentation: # @raycast.description Copy From ChatGPT # @raycast.author Nansen Li # @raycast.authorURL nansenli.com
# Get clipboard content clipboard_content=$(pbpaste)
# Check if content was successfully retrieved if [ -z "$clipboard_content" ]; then echo"Clipboard is empty or inaccessible." exit 1 fi
# Process clipboard content modified_content=$(echo"$clipboard_content" | \ sed 's/\\\[/$$/g; s/\\\]/$$/g; s/\\( /$/g; s/ \\\)/$/g')
# Write the modified content back to the clipboard echo"$modified_content" | pbcopy
After creating the script, we need to add the directory containing the script to Raycast.
In this step, select the directory where the script was just created. At this point, we can see the newly created script in Script Commands.
How to Use
After copying a formula from ChatGPT, open the Raycast panel, find the newly created script, and run it. The clipboard content will be automatically fixed. Then, simply paste it into Obsidian or Craft.
I’m Nansen, and I participated in the 2024 Huawei Ireland Research Center Server Cluster Management Optimization Competition. Here, I’d like to share my experience in this competition and summarize some key takeaways.
We achieved first place in the algorithm section, scoring approximately 4%-5% higher than the second to fourth places, giving us a significant advantage. However, we faced considerable challenges in the presentation segment. First, we recognized that there is room for improvement in our English fluency. Second, we found that our presentation slides could be more polished and visually appealing. Lastly, we encountered some challenges with time management. Nevertheless, despite these obstacles, we still managed to secure third place overall.
Competition Process
The competition was divided into two stages. The first stage allowed ample preparation time. Once we settled on using the simulated annealing algorithm, we began developing it. The main difficulty in this stage was optimizing and understanding the requirements of the task. During development, we encountered numerous bugs, but after fixing them, our score improved significantly.
In the second stage, as the problem was released on the day of the competition, I continued optimizing the algorithm from the first stage, successfully increasing the evaluation speed by 1000 times. This significantly boosted our performance in the second stage, providing us with enough strength to vie for first place.
In the final round, our algorithm performed very consistently, and after some adjustments, we took a considerable lead over our competitors. However, because we didn’t put enough emphasis on making an effective presentation, we mistakenly believed that high algorithm performance alone would guarantee a top score, which proved to be wrong.
Lessons Learned
Algorithm Choice
Fortunately, I chose the right algorithm from the outset, and shortly after the problem was released, I devised a framework that suited the entire competition. However, I did take some wrong turns, such as attempting impractical algorithms like PPO. After initial trials failed, I should have moved on instead of wasting further effort. Given the limited time, we should focus on achievable optimal results within the shortest period rather than pursuing ideal but unrealistic solutions. It’s also crucial to recognize one’s limitations and concentrate on goals that are achievable in the available time.
Team Collaboration
Luckily, our team division was reasonable this time, and I did my best to ensure every member could contribute their value. One area for improvement is communicating more with team members to understand their ideas and preferences. Since I mainly handled the algorithm part, I had relatively little interaction with teammates, which I will work to improve next time.
Presentation Design
We didn’t anticipate that the level of presentation skills from other teams would be so high. My teammates speculated that some competitors might have a business background, giving them an advantage in crafting presentations. Moreover, they had five members in their team while we only had three, which put us at a disadvantage regarding manpower. These were objective challenges, but if we had paid more attention to creating our presentation, the first prize could have been within our reach.
Over-committing Leading to Imbalance
In the final round, our algorithm was already quite excellent, and our score surpassed the previously top-ranked team. However, I continued spending considerable time on further optimizations. Even though we were significantly ahead, this focus caused us to neglect the preparation of our presentation. In hindsight, I should have known when to stop and fully recognized the importance of balancing different aspects of the scoring criteria.
Conclusion
Participating in the Huawei Tech Arena 2024 competition provided me with invaluable experience. The competition highlighted our strengths, but also revealed areas where we need to improve in terms of showcasing skills and team collaboration. Looking ahead, I will keep these lessons in mind and strive to continuously improve myself in future competitions. If you have any questions, feel free to leave them in the comments section.
Today, I began the long journey of practicing Leetcode problems. Previously, I only did a few problems to maintain familiarity, but today, I officially started preparing for interviews.
I have been thinking about how to efficiently solve Leetcode problems. In my opinion, to be efficient, one must memorize problems. Just as reading a book a hundred times reveals its meaning, training a language model through extensive practice hones its coding skills. Similarly, with Leetcode, through repeated practice, the answers will come naturally; quantity brings quality.
This code better reflects the essence of dynamic programming.
To understand the formula dp[i] = max(nums[i] + dp[i-1], nums[i]), we can analyze it from a dynamic programming perspective. The core idea here is to make the optimal choice at each position. Here is a detailed explanation:
1. What does dp[i] represent?
dp[i] represents the maximum subarray sum ending at position i.
2. Why compare nums[i] + dp[i-1] and nums[i]?
The key question is: Should the current maximum subarray include the previous part (dp[i-1])?
nums[i] + dp[i-1]: If dp[i-1] is positive, adding the current nums[i] will increase the subarray sum, so we choose to add it.
nums[i]: If dp[i-1] is negative, we choose to start a new subarray from the current position, as a negative sum will only drag down the current sum.
3. Why not compare subsequent numbers?
When making the comparison, we assume the subarray stops at position i. In other words, we consider the maximum value within the range [0:i]. At position i, we either add the previous subarray or abandon it and only use the current number.
We then traverse the entire array, finding the maximum value at each position, and finally return the largest value.
This is a classic interval merging problem, where we need to merge a new interval into existing intervals.
The solution can be broken down as follows:
Step 1: Add all non-overlapping intervals that come before newInterval to the result.
Step 2: Merge all potentially overlapping intervals with newInterval. Note the conditions for merging.
Step 3: Add the remaining intervals to the result.
Note that the condition for merging intervals is that the start of the previous interval is less than or equal to the end of the subsequent interval, i.e., intervals[i][0] <= newInterval[1].
while i < len(intervals) and intervals[i][1] < newInterval[0]: ret_list.append(intervals[i]) i += 1
while i < len(intervals) and intervals[i][0] <= newInterval[1]: newInterval[0] = min(intervals[i][0], newInterval[0]) newInterval[1] = max(intervals[i][1], newInterval[1]) i += 1
ret_list.append(newInterval)
while i < len(intervals): ret_list.append(intervals[i]) i += 1
return ret_list
With careful attention to detail, this problem is not difficult.
classSolution: defisSubsequence(self, s: str, t: str) -> bool: i = 0 j = 0 while i < len(s) and j < len(t): if s[i] == t[j]: i += 1 j += 1 return i == len(s)
This problem can be solved using a two-pointer technique, with t as the base. If s contains matching characters, we move forward; if we reach the end of s, it means the match is complete.
This problem asks us to find how many distinct subsequences of string s equal string t.
First, we need to define dp, where dp[i][j] represents the number of distinct subsequences that can be formed from the first i characters of s to form the first j characters of t.
dp[i][0] represents when t is an empty string, the result is 1.
dp[0][j] represents forming t from an empty string, which results in 0.
For dp[i][j], the result depends on the characters at positions i and j:
If they are equal, the result is the sum of the cases where s[i-1] is not matched (dp[i-1][j]) and the cases where it is matched (dp[i-1][j-1]).
If they are not equal, the result is equal to dp[i-1][j].
Note that i, j refer to the first i and j characters.
Additionally, dp[0][0] is initialized to 1, as an empty string is a subsequence of any string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution: defnumDistinct(self, s: str, t: str) -> int: dp = [[0for _ inrange(len(t) + 1)] for _ inrange(len(s) + 1)] for i inrange(len(s) + 1): dp[i][0] = 1
for j inrange(1, len(t) + 1): for i inrange(1, len(s) + 1): if s[i-1] == t[j-1]: dp[i][j] = dp[i-1][j] + dp[i-1][j-1] else: dp[i][j] = dp[i-1][j]
The answer provided for exploiting this vulnerability is:
1
perl -e 'system "./obo", "\x38\x84\x04\x08"x256'
The result of running this command is that multiple lines of I've been hacked are printed on the screen.
Analysis
When the program enters the foo function, the memory layout looks like this (as observed using GDB):
From top to bottom, the layout contains the return address, the saved frame pointer, and the buffer (buf).
When the line buf[sizeof(buf)] = '\0'; is executed, the least significant byte of the saved frame pointer (ebp) is set to 0. To ensure that ebp still points within the buf region after being partially overwritten, a buffer of at least 1024 bytes is required. Specifically, ebp needs to be overwritten such that it remains within a reasonable range (— up to 0xff), which is why the buffer is set to 0xff * 4 bytes.
Understanding Assembly Commands on foo Return
When the foo function returns, it typically executes the following key assembly instructions:
1. leave Instruction
The leave instruction is equivalent to:
1 2
mov esp, ebp pop ebp
mov esp, ebp: This sets the stack pointer (esp) to the value of the frame pointer (ebp), restoring the stack pointer to the top of the current stack frame and effectively releasing the space occupied by the current function.
pop ebp: This pops the value at the top of the stack and assigns it to the frame pointer (ebp), thereby restoring the caller’s frame pointer. Essentially, it writes the return address into ebp, meaning it assigns the stack value (usually the caller’s frame address) to ebp, restoring the caller’s stack frame.
The effect of leave is to restore esp to its state before the function was called and to pop the saved ebp. If ebp has been overwritten to point to a special address (such as an address within the buffer), it can result in an incorrect stack pointer location during function return.
2. ret Instruction
The ret instruction pops an address off the top of the stack and jumps to that address:
1
pop eip
If the return address has been overwritten with the address of the bar function, the execution flow will jump to bar, allowing an attacker to run arbitrary code. Essentially, ret pops an address into the instruction pointer (eip) and jumps to that address to continue execution.
Attack Steps
When the command perl -e 'system "./obo", "\x38\x84\x04\x08"x256' is executed, the program takes these repeated bytes as the input to ./obo.
As the foo function returns, the leave and ret instructions are executed, leading to the return address being overwritten. This causes the program to jump to the bar function, printing the success message multiple times.
Further Analysis: Determining Effective Overwrite Locations
Stack Frame Layout Explanation
During the GDB debugging session, the memory layout for the stack frame of the foo function looks like this:
Return address: Located at 0xbfffed10, this is the address that the program will jump to after the foo function finishes executing. Overwriting this address can control the flow of the program and potentially redirect it to malicious code (e.g., the bar function).
Saved frame pointer (ebp): Stored at 0xbfffed0c, this value is used to restore the calling function’s stack frame after foo finishes. In this example, we can see how the off-by-one overflow can overwrite the least significant byte of ebp.
Buffer (buf): The buffer starts at address 0xbfffe90c and extends to 0xbfffed0b, with buf[0] located at 0xbfffe90c and buf[1023] at 0xbfffed0b. The vulnerable line in the code, buf[sizeof(buf)] = '\0';, writes a null terminator (\0) just outside the bounds of this buffer, affecting the saved frame pointer.
In the off-by-one overflow scenario, the write operation overwrites the least significant byte of ebp, which is stored at 0xbfffed0c. By manipulating the value of ebp, we can influence the stack behavior when the leave and ret instructions are executed, eventually allowing us to control the program flow and redirect execution to the bar function.
To perform a successful attack, it’s crucial to determine precisely which bytes need to be overwritten in order to manipulate the control flow effectively. In this example, the overflow occurs when buf[sizeof(buf)] = '\0' is executed, causing the least significant byte of the saved frame pointer (ebp) to be set to 0. Thus, the value of ebp needs to be adjusted to ensure it points back into the buffer area, allowing the execution to proceed in the desired way and eventually jump to the bar function.
Based on further analysis and testing, the following insights were obtained:
To accurately determine the overwrite location, the value of ebp is crucial. However, obtaining this value is challenging because:
GDB debugging affects address layout.
The length of the input parameter affects the address layout.
Under GDB debugging, the layout within the foo function looks like this:
After executing buf[sizeof(buf)] = '\0';, ebp is modified such that the return address effectively takes the value at ebp + 1, which is the address 0xbfffed00 + 1, or 0xbfffed04.
The corresponding offset is at position 255 in buf, meaning the attack can be constructed by filling in the return address only at that specific location. The following command was used for verification in GDB:
1
r $(perl -e 'print "\x01\x01\x01\x01"x254 . "\x38\x84\x04\x08"x1 . "\x01\x01\x01\x01"x1')
This was verified to work under GDB debugging, with some details to note:
The input parameter length must always be 256 bytes; otherwise, the value of ebp will change, as the input parameter occupies stack space, affecting the starting position of the frame and thereby affecting the value of ebp.
Padding must use non-zero values such as 0x01, because strncpy will terminate early if it encounters a 0 value.
When executing the program directly (i.e., without GDB), the memory layout differs, resulting in a different offset position. Through experimentation, it was found that the offset is at position 235. The corresponding attack command is:
// Write the modified content back to the clipboard await navigator.clipboard.writeText(modifiedContent);
newNotice("Clipboard content has been processed and modified!"); };
2. Set Up the Script in QuickAdd
Install the QuickAdd plugin and create a Macro, configuring it as shown below, then save it. The first step in the Macro is to execute our user script fixlatex.js, the second step is to wait for 100 milliseconds, and the third step is to execute the paste action.
3. Set Sidebar Shortcut in Commander
Install the Commander plugin and set up the QuickAdd action we just created as a sidebar shortcut. You can also skip this step and directly use an Obsidian command to execute this action.
4. Verify the Effect
Now, on the ChatGPT webpage (currently there seems to be an issue when clicking the copy button in the app), click the copy button, then in Obsidian, click the sidebar shortcut or manually execute the QuickAdd command. This will copy the content from ChatGPT to Obsidian and automatically convert the LaTeX format.
Hello everyone, my name is Nansen Li, previously known as Nan Li. I’m from China and a technology-loving engineer. I hold a bachelor’s degree in Mechatronic Engineering and two master’s degrees in Computer Science. I previously worked as a Go Language Engineer at a major internet company in China, and I am currently pursuing a master’s degree at a university in Dublin.
I completed my undergraduate studies in Mechanical and Electronic Engineering, during which I participated in the National College Students Electronic Design Contest and the Intelligent Vehicle Competition held in China. Over time, I became increasingly interested in programming, which led me to pursue a Master’s degree in Computer Engineering to follow my true passion. During my Master’s studies, I continued to engage in programming-related competitions and interned at a major Internet company. I was fortunate to secure a full-time position at the company as a Software Engineer, where I worked for three years.
During my time at work, I had the privilege of developing software for hundreds of millions of users and directly serving customers. Every time I deployed a service, I was extremely careful because I knew that what I was releasing was not just cold lines of code but something that would impact the experience of thousands of users.
To help my family business recover from the pandemic, I left the company to support my family. At the same time, I began strengthening my foreign language skills and applied for an overseas study opportunity. Now, I have arrived in Ireland to further deepen my knowledge in computer science.
I am deeply interested in frontend and backend development, system architecture, algorithms, game development, and generative AI (e.g., Stable Diffusion and ChatGPT). I’ve always been dedicated to improving my programming skills and enjoy experimenting with new technologies, keeping myself sensitive to industry trends.
If you share similar interests in technology or lifestyle, feel free to reach out to me. We could discuss and exchange ideas together.
I am Nansen Li, and this is my first note. I don’t know how much I can document, nor how long I can keep this up, but I will do my best to stay consistent with my entries.
