Tuesday, November 29, 2022
No menu items!
HomeTECHCryptographic Challenge: How to guess the password on a fake keyboard |...

Cryptographic Challenge: How to guess the password on a fake keyboard | technology


EscapaEsp, which designs challenges for escape rooms, received a commission from a YouTube channel: a competition in which teams of 10 people face different tests. The official of the channel is famous YoutubeHe wants to offer a great prize to the winners, but to do so, he wants to make absolutely sure that only three teams out of ten win. Also, you may want to give the impression that winning the game is hard.

Julia and Juan, who are responsible for designing challenges at EscapaEsp, brainstorm until they come up with a proposal. Each team must face different tests to find ten characters of the password. At the end of the tests, all teams will move to a final stage in which the members of the opposing group one by one enter a room with only a keyboard and monitor. Each letter will type one character of the password. To win, they must get on the computer screen to display all 10 characters of the password in the correct order.

The test, of course, will not be easy. Not even for computers that know the password perfectly: the keyboard is manipulated, so that what is written on the keyboard does not correspond to what is on the screen. Specifically, Julia and Juan suggested the following rules:

1) The password does not contain any duplicate characters, and the characters can only be among the following 40 characters: the 27 characters of the Spanish alphabet (with “ñ”), the period, the hyphen, the comma and the ten digits (0-9).

2) The keyboard has only 40 characters above. In addition, the cables were tampered with randomly, so that when you press a key, most likely, the pressed letter will not appear on the screen. That is, pressing the “m” key may display the letter “8”. However, this manipulation remains the same throughout the game (if the “m” key appears in the number “8”, then this is done for all players on the same team). Also, no two keys will display the same character on the screen.

3) Players who entered the console room will need to exit through a different door than the entrance, and will not be able to communicate with players who are still waiting for their turn. Likewise, even if spectators were able to view what was happening in the keyboard room, players who did not enter should not know anything. That is, each player on the team entering the keyboard room must have the same information as the first player who encountered the keyboard.

4) The characters of the password must be entered in order: the first player to enter the room must enter the first letter, the second enters the second letter, and so on.

5) When the player faces the keyboard, he will be able to try out a maximum of 20 different keys to show his character. The moment the correct character appears, the green light will be on and the next player can move forward, regardless of whether the player knows the correct character or not before entering. If after the 20th victory any player fails to get the green light, the whole team loses.

6) Ten players can cooperatively design a strategy before facing the game.

The Youtube He makes a quick calculation and determines that the probability of success of each team member is ½. Since they all have the same information when entering, being 10 players on the team, their probability of success is ½ * ½ * … * ½ (10 times), about 0.001. This shocks him for two reasons. First of all, the probability of winning appears to be independent of whether the password is known or not, as the computer automatically validates the key when the correct character is entered. And this seems unfair to him: the team that knows the entire password should have an advantage. Secondly, this possibility seems very slim to him. Having teams that win makes more people interested in the program. Also, more teams would like to participate.

However, Julia and Juan explain that there is a strategy that ensures that the team’s probability of success, if they know the entire password, is 0.32. If they only know some parts of the password, the probability of winning will be reduced: for example, if they know 7 characters, they cannot find a strategy that offers success with a probability greater than 0.04.

Can the reader tell what this strategy the contestants have to follow to win three times out of ten if they know the entire password? Why is it so important to know the password to increase your chances of winning?

Crypto challenges will be posted every 15 days. Readers can leave their solutions and discuss the problem in the comments on this page, so anyone who wants to solve it on their own is advised not to read it until the puzzle is solved. You can also email your responses [email protected]. In each new challenge, we will post the previous solution, along with a comment with some of the original or inspiring ideas we received.


Diego Castejon Molina s David Balbas Gutierrez Pre-doctoral researchers at the IMDEA Software Institute in Madrid. His work focuses on the design and analysis of encryption protocols and applications.


A solution to the previous challenge

We’ve had many responses this week, thank you all for your comments!

To calculate the correct order, we use the mentioned mechanism, which, although simplified, is the one followed by the Bitcoin cryptocurrency, proposed in 2008 under the pseudonym Satoshi Nakamoto. Basically we are looking at the value of BA, which is a pointer to the previous block. Specifically, BA refers to the remainder of calculating the integer division of the previous block by 541. Thus, for example, the second block is found by calculating the integer division of 53244 by 541. The remainder, 226, tells us what the second block (which contains 226 as BA). By the same procedure, we can find the third block. When calculating the integer division of 22623138 by 541, the remainder, 141, declares the third block. To calculate the fourth block, you will first have to calculate the value of B for the third block. Remember, it’s about finding a value like 141112XXXXX (where X is different numbers, length is not a constant) so that when calculating the integer division of 141112XXXX^3 and 541, the remainder ends with two zeros. It’s about testing values ​​(there is a suggestion to program them with a table style command[H[141112*10 + k]{k, 0, 9}]If we assume that we find the solution by adding a single number― or a table[H[141112*10^2 + k], {k, 0, 99}]― for a two-digit test― etc.). With this technique, it is obtained that 39 achieves. Thus, we can calculate the value of BA for the fourth block, which will be the remainder of the calculation of the integer division between 14111239 and 541. The result is 336 declaring the fourth block. Thus, the rest will be the last of the blocks.

Photo provided by our reader David.
Photo provided by our reader David.

Note: For those who know modular arithmetic, the operations we perform when calculating the divisions of integers and keeping the remainders, are calculating the divisor of the divisor.

Once the blocks are sorted, we can see the money the brothers have. We aggregate the result into the following table, where the last column is the final result.

Although, as many of you have pointed out, if there are no invalid blocks, the transactions proposed in the challenge will “turn”, and given the final balance the solution is the same, if the blocks are not arranged correctly, we can’t think of the right solution . The reason (very important in the real world) is that ordering blocks in any way often leads to invalid intermediate transactions: that someone has to transfer more than they currently have.

NB: Apart from simplifying the contents, the importance of formats must be kept in mind, which is also simplified here to focus the explanation on the mechanism. Some of you may be familiar with the concept of a summary function (or hashes) which are used in many everyday scenarios, from digital signatures to when the password is saved. What a miner does when a miner does not compute a cube of certain values, but will conveniently compute a hash function, especially one of the most used today, the SHA-256 function. For simplicity, we’ve also omitted the (very important) part where messages are authenticated, and digital signatures are very useful in this context.

: As promised last week, we also included the solution for The music coding challenge sent to us by our reader Salva Foster.

– What melody acts as a key (keep in mind that the letter F in the key is actually an F)?

Bach’s first cello suite BWV 1007.

– What is the hidden word?

our end

– What is the system that allows the message to be encrypted/decrypted?

To encode a message, we just convert it to binary, as in the challenge A message in the symbol of Naples is hidden between ones and zeros Starting from a certain previously selected melody (which acts as a key), we create a new tone in such a way that it contrasts the main melody to get 0, and the consonant to get 1. In particular, the alternation of the lower and higher musical notes was chosen from those of the dissonance key, and a perfect fourth (or fifth perfect) for symmetry, although it could have been made more complex by random selection of other types of repulsion and symmetry.

To decode it, one can only do the same, but in the opposite direction, i.e. determine the dissonance and harmony of the received melody with respect to the melody that acts as a key to convert it to the corresponding forms 0 and 1, and, accordingly, transform the binary code obtained in the clear message .

Another indefatigable reader, Xuacu Álvarez, found the right solution (congratulations, he didn’t say better than that), although there was some suspicion that we’re breeding here:

“I humbly think, due to my ignorance of the musical language, that there is an error in the manifest data, because with the melodies presented a slightly flawed result is obtained (ENHPSABVENA) but this actually allows us to sense the hidden message.

May I suggest a correction in the key that reflects the harmony/dissonance on the fifth note of the fourth band, on the fourth and fifth notes of the fifth band, and on the fifth note of the eighth band.

Original key GDBAB – DBDGD – BABDB – DGECB – CECEG – ECBCE – CEGFC – BCFCF – GFCBC – FCFGG – BABGB

Debug Key GDBAB – DBDGD – BABDB – DGECF – CECGB – ECBCE – CEGFC – BCFCC – GFCBC – FCFGG – BABGB”.

The modest musical knowledge of those coordinating this section prevents us from clarifying whether or not this last nuance is true, but we congratulate you on solving the challenge and as always thank you for your contribution.

You can follow EL PAÍS TECNOLOGÍA at Facebook s Twitter Or sign up here to receive Weekly Bulletin.



RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments