Stripe CTF - SHA-1 algorithm vulnerability analysis
When a post was published on Habré that Stripe is holding a Capture the Flag contest, I immediately registered as a participant.
Each of the nine levels represented the task of hacking the system and obtaining a password to the next level. Passwords could be stored both in databases and files, and in memory. By the way, all the code was open, so the tasks were reduced to analyzing the code for vulnerabilities, it was not necessary to poke blindly.
Levels from 0 to 6 were not difficult - standard SQL and JavaScript injections, uploading a PHP script to the server instead of a picture, etc.
')
But the 7th level makes me break my head ...
Stripe programmers, inspired by the TacoCopter service, modeled a certain WaffleCopter - a service for the delivery of waffles to any specified point using a radio-controlled (or maybe fully automated) helicopter.
The service provides an API for waffles. The database contains information about users and types of waffles available for ordering. There are several types available for ordering only premium accounts.
CTF participants were provided with a regular account and the task was to order a specific type of premium waffles - Liège Waffles. As a bonus, a log of requests was published, so that you could see who ordered what and when.
Each request must be signed using the SHA-1 algorithm according to the following principle:
Then the message is sent to the server using the POST method.
In the logs I found the following query:
(unfortunately, the server is already unavailable, so I substituted my values in the request body)
Here user_id is the user ID, lat and long are the coordinates of the place where the order is delivered, count is the number and waffle is the order type itself. Of course, the type of waffles does not correspond to those that we must order, otherwise everything would be too easy.
Since before our eyes there were logs of requests from premium users, the first thought that came to mind was “can I figure out the secret from two messages and two hashes?”
Of course, this option immediately disappeared, since SHA-1 is not so simple an algorithm.
After reading Wikipedia and a little googling about SHA-1, I found that it is not recommended to generate a signature like this:
The main loop SHA-1 iteratively processes 512-bit blocks into which the original message is broken. By calculating and rearranging the block, five 32-bit words are formed at the output of each iteration, which are the input parameters of the next iteration. After the last iteration, these parameters are combined into a 160-bit hash.
The essence of the attack by lengthening the message is as follows. Another 512-bit block, consisting of an additional message, which we want to transmit to the server on behalf of another user, as well as service information, in particular, units, complementary zeros and message length, is initialized. The 160-bit hash of the original message known to us is divided into five 32-bit words and an additional iteration is carried out, where the calculated words are input parameters. Above our block, the necessary operations are performed and at the output we get new five words, which will be the new 160-bit hash.
We supplement the original message with ours, replace the original hash with the computed, and voila: the server accepted our request.
At the same time the server will receive something like
We added the wafer type we need to the original message. In response to the request, we will receive a confirmation code, which, in the case of the order of Liège Waffles, will be a password to the next level.
As a measure to counter this type of attack, double hashing is recommended.
Each of the nine levels represented the task of hacking the system and obtaining a password to the next level. Passwords could be stored both in databases and files, and in memory. By the way, all the code was open, so the tasks were reduced to analyzing the code for vulnerabilities, it was not necessary to poke blindly.
Levels from 0 to 6 were not difficult - standard SQL and JavaScript injections, uploading a PHP script to the server instead of a picture, etc.
')
But the 7th level makes me break my head ...
Stripe programmers, inspired by the TacoCopter service, modeled a certain WaffleCopter - a service for the delivery of waffles to any specified point using a radio-controlled (or maybe fully automated) helicopter.
The service provides an API for waffles. The database contains information about users and types of waffles available for ordering. There are several types available for ordering only premium accounts.
CTF participants were provided with a regular account and the task was to order a specific type of premium waffles - Liège Waffles. As a bonus, a log of requests was published, so that you could see who ordered what and when.
Each request must be signed using the SHA-1 algorithm according to the following principle:
= sha1 ( + )+= "|sig:" +Then the message is sent to the server using the POST method.
In the logs I found the following query:
user_id=1&lat=26.629166676667&long=-70.883611121111&count=1
&waffle=dream|sig:439ca26828fb91eb8525274ecb9ef241f0487c88(unfortunately, the server is already unavailable, so I substituted my values in the request body)
Here user_id is the user ID, lat and long are the coordinates of the place where the order is delivered, count is the number and waffle is the order type itself. Of course, the type of waffles does not correspond to those that we must order, otherwise everything would be too easy.
Since before our eyes there were logs of requests from premium users, the first thought that came to mind was “can I figure out the secret from two messages and two hashes?”
Of course, this option immediately disappeared, since SHA-1 is not so simple an algorithm.
After reading Wikipedia and a little googling about SHA-1, I found that it is not recommended to generate a signature like this:
sha1 ( + ) , since this method is not sufficiently reliable. At the same time, I received a hint from my American friend, who at that time had already successfully solved this quest: length-extension, or an attack by lengthening the message, which is also mentioned in Wikipedia. Well ... I didn’t even think that SHA-1 is so vulnerable.The main loop SHA-1 iteratively processes 512-bit blocks into which the original message is broken. By calculating and rearranging the block, five 32-bit words are formed at the output of each iteration, which are the input parameters of the next iteration. After the last iteration, these parameters are combined into a 160-bit hash.
Watch the video, how the algorithm works.
The essence of the attack by lengthening the message is as follows. Another 512-bit block, consisting of an additional message, which we want to transmit to the server on behalf of another user, as well as service information, in particular, units, complementary zeros and message length, is initialized. The 160-bit hash of the original message known to us is divided into five 32-bit words and an additional iteration is carried out, where the calculated words are input parameters. Above our block, the necessary operations are performed and at the output we get new five words, which will be the new 160-bit hash.
We supplement the original message with ours, replace the original hash with the computed, and voila: the server accepted our request.
At the same time the server will receive something like
user_id=1&lat=26.629166676667&long=-70.883611121111&count=1
&waffle=dream%01%00%00%00%00%00P&waffle=liegeWe added the wafer type we need to the original message. In response to the request, we will receive a confirmation code, which, in the case of the order of Liège Waffles, will be a password to the next level.
As a measure to counter this type of attack, double hashing is recommended.
Source: https://habr.com/ru/post/151682/
All Articles