Hacking Bitcoin on TV: obfuskuy, not obfuskuy, still get QR

The story about how the secret key for Bitcoin in the form of a QR code was restored from the smeared picture

We could just call this post “How good is the QR code and how we restored it from almost nothing.” But it is much more interesting when the QR code is the key to the wallet worth $ 1000 in cue ball.

Part of a documentary film where Roger Ver talks about Bitcoin wallets.

')

Before we begin, I will answer: we do not know the journalists who recorded the interview, and we do not know Roger W. Anyone who had access to this video could get the secret key.

Bitcoin, Ethereum, Litecoin, Dash, Neo ...

Cryptocurrencies are everywhere and are developing rapidly. As for me, I’ve been watching bitcoin since 2013 (but that doesn’t mean I’m buying). I had to read “Mastering Bitcoin” 3 times to understand how each part of it really functions and to be able to explain it to others. Still, I cannot keep up with the modern market, new cryptocurrencies, algorithms, new ICOs are everywhere and appear every day.

It is easy to start using cryptocurrency by following online tutorials. You simply download any wallet application, create a pair of keys and buy a cryptocurrency on one of the exchangers, but at the same time, the cryptocurrency learning curve is rather complicated.

And if you do not fully understand how each part of this mechanism functions, you should avoid working with cryptocurrency, otherwise you risk losing your money if you fall into one of the many traps. One of them, keeping your secret key safe, is the topic of this post.

The basic rule of the "Cryptographic Club": do not share your secret key with others.

The most important thing you have when working with cryptocurrency is your secret security key. If you lost it, you can say you lost your money. If someone gains access to your security key, you will also lose your money. It's simple.

Using a real example, we will show you how step by step we restored the secret key $ 1000 of a bitcoin wallet created by @rogerkver for the French TV show “Complément d'enquête”, although it was smeared.

Introduction

Last week, France 2 broadcast a bitcoin documentary. They interviewed @rogerkver, who decided to offer $ 1,000 in Bitcoins for the fastest viewer. Unfortunately, the QR code and the secret key were smeared by France 2.

Figure 1. Difficult QR code and secret key.

I saw several people complaining about this on Twitter, and some even left tweets claiming that “France 2” decided to keep Bitcoins for themselves. This is an erroneous assumption, “France 2” closed the QR code not because it wanted to hold Bitcoins, but because it was legally obliged.

You can try to scan the QR code with as many applications as you can but you will not be able to decrypt it because of the strong blurring.

The story could end at this point, $ 1000 would be lost forever, because I do not think that Roger Werth kept a copy of the secret key. Only interview journalists can buy out the bitcoins.

But, at the very end of the interview, they showed a small part of the QR code. Did they do it on purpose, knowing that $ 1,000 would be lost if no one could find the secret key? Or was it one of the mistakes you can make when starting to use cryptocurrency?

Figure 2. The open part of the QR code and the smeared string with the key below.

I was going to write to my friend @clementstorck when I received a screenshot of the QR code he took. We decided to work in order to find out whether it is possible to obtain the secret key with such a small amount of information.

Let's be honest, the chances of finding the secret key using only brute-force search were close to zero. We knew the properties of QR codes and their resistance to damage. Our goal was to gather as much information as possible, in order to reduce the number of unknown parameters to a minimum. We knew that at some step, let's resort to busting. After all the steps below, we had to go through a total of 2,097,152 combinations =).

So where do we start? Below are all the steps we took to get the secret key.

Collection of information
Let's poshaman. Image processing.
Standard QR code, part 1
QR code reconstruction
Standard QR code, part 2
QR code decoding
Error correction code
Python Brutus

1. Collecting information

The first step was to collect as much information from the interview as possible. We observed the playback frame by frame and took several pictures, such as:

The public key that leads us to the (almost) empty BTC wallet . Roger Ver lied? Many people talked about this on Twitter. He did not lie, on his twitter post is posted, where he talked about the sale . We had to look for a bch wallet .

Figure 3. Public key and QR code: 17Qgadvc7pm51mV9r9zUAs4xU1XXwDRr8o

Blurred part of the line with the access key. We will use it at the stage of image analysis to get the first 6 letters. The error correction step will give us the next 7 letters.

Figure 4. An anointed part of the string with a secret key. You can make out a few words, but basically the picture is not clear.

The last letter of the secret key will also be useful for unlocking the 8 extreme characters of the key.

Figure 5. The last letter is well distinguishable V.

Screenshots of poor quality at the top and bottom of the QR code. They will also be useful to get (some) more data and fill in the QR code during the recovery phase.

Figure 6. Top of the QR code, the first line can be used.

Figure 7. What, seriously ?? The left part of the QR code, the first two columns, can also be (partially) used.

The tool he used to create public and private keys is the Single Wallet tool on Bitcoin.com . This gave us information about the data inside the QR code: 32 Bitcoin wallet tivol key similar to this.

KwjiU4CVAmdyxyDbvkbx2XbSoU1nxZgyXz7usqAemvsd4RdGHoPF

The next step is to recreate a QR code.

2. Poshaman. Image processing

Well, at this stage we have less than 1/3 of the QR code, we are still far from the secret key. What can we learn from screenshots?

We decided to focus on 2 screenshots, the first is a blurred QR-code of the secret key, we wanted to know if QR-code applications can read it after processing.

The second screenshot we wanted to work on had a small part of the secret key. We knew that we needed to have at least a small amount of data if we wanted the Error Correction Code (ECC) to work.

We decided to send screenshots to our experts. With a lot of results :)

This is what we got after partially removing the blur effect.

The version of the QR code after processing was also not decoded by any of the applications for reading the QR code. We decided to try, because this guy conducted some tests on QR codes, and in the comments confirmed that they are scanned

Figure 8. We did not find anything in this photo. Only confirmation of the last letter.

Two non-blurred versions of the secret key string. The first gives us the first four letters (we clearly do not see "K"), and the second gives the first six letters (we do not see the "z").

Figure 9. The photo is not clear, but you can see “yUz”.

Figure 10. You can read the first 6 characters of “KyU? SR”

Leave this information for later. She will help us make up a few bits later.

3. Standard QR code, part 1

It was important to understand how QR codes work and the limitations of their ECC capabilities in restoring a damaged QR code.

Wikipedia is a good start, but all we needed was in ISO / IEC 18004 (there is a free version of the first edition on Swisseduc ). We also found this treasure online.

Figure 11. Error Correction Level and the QR Code Mask can be extracted from this screenshot.

Before we begin to reconstruct the QR code, let's see what we can extract from this image using the ISO standard and the structure of the QR code.

Figure 12.

Interesting for us was the blue bar (x: 8, y: 22-28).

This is part of the format information line (15-bit sequence, 5 data bits and 10 BCH error correction bits). The bits located at (x: 8, y: 22-28) are bits 8-14 lines. We had only 7 bits out of 15, but that was enough to find the information we need.

The format information line encodes the error correction (EC) level and mask pattern applied to the QR code. There are 4 possible EC levels (L, M, Q, H) and 8 possible mask patterns => 32 possible information formats of information.

Details on how to create an information line can be found on page 76 of the standard (Appendix C - Format Information). A list of 32 options can be found here .

Figure 13.

Top down. We have bits from 8 to 14 of the information line. Bit 14 is the most significant. In screenshot No. 11 we can read it.

0011001XXXXXXXX

Quick search in the table of information format lines. The only combination that corresponds to the one that corresponds to the ECC level: And has a mask: 3

Figure 14.

We also needed to find a QR code coding format. There are five different encoding formats (each of them uses its own method for converting text into bits):

Numeric (0-9)
Alphanumeric (0-9; AZ; nine other characters: space $% * + -. / :)
8-bit byte (JIS character set 8 bit. JIS X 0201 Japanese version os ISO 646 )
Kanji (JIS Shift character, can encode each kanji character in 2 bytes)
ECI (Extended Channel Interpretation, if you need special / custom encoding)

The QR code coding format is an 8-bit Byte type , the numeric and alphanumeric type are not supported by the alphabet of the secret key (no lowercase letters), Kanji encodes 2 bytes each (we need only one), and ECI is brute force .

We were almost ready to begin the reconstruction of the QR code, the last thing we needed to know the size of the QR code.

There are 40 varieties of QR code sizes (called versions). They can start from 21x21 pixels (version 1) to 177x177 pixels (version 40). They grow by 4x4 pixels each time they increase their version number. Each version has a maximum capacity based on the coding format and error correction level.

The capacity of each QR code depends on its version and error correction level. Details can be found on page 28 of the ISO standard.

We knew that the QR code should have stored 52 characters (416 bits) with an error correction level of H.

Figure 15. V6 is the smallest size that can hold a 416-bit key with an error correction level of H. V5 is too small, V7 is too large.

Size of QR code 6th version 41x41px.

Now we had all the information necessary to start the reconstruction of the QR code.

4. Reconstruction of the QR code

We know that we had to restore a QR code of 41x41 pixels. We decided to work on the Google spreadsheet (where it is easy to draw and use functions such as masking a QR code).

We completed the following steps:

Draw each template that is part of the standard (positioning template, alignment template (only one from QR code version 6), synchronization template and dividers, as shown in Figure 12)
Add bits from the format information string found in the previous step.
Fill in the rest of the QR code based on the screenshot 11 we took.

Let's also use the top and left screenshots of the QR code. It is not so much, but at this stage every bit matters.

Figure 16. As we collected a few more bits in the upper rows.

Figure 17. The same process for the left side of the QR code (rotate 90 °)

Below is a QR code that we were able to recover. The next step is to define a sequence of bits to extract the code words and error correction code words.

Fig. 18. Step-by-step reconstruction of the QR code.

5. Standard QR code, part 2

We needed to understand how to read a QR code if we want to extract more bits from it.

A QR code consists of data code words and error correction code blocks .

Each block has a length of 8 bits, and each bit is represented by a module (black or white square). You cannot say just looking at a QR code that a specific white square is “0” or “1”, because, as we will see later, a mask is applied to the QR code before its visualization.

The data code words contain the message / data encapsulated in a simple protocol, shown below (details can be found on page 17 of the ISO standard):

Mode Indicator: 4 bit identifier indicating in which encoding mode the message / data sequence is encoded.
Number of characters indicator: a sequence of bits that indicates the length of the message. Changes according to the coding mode and the version of the QR code.
Message / data flow (secret key). (8 bits per character)
Terminator: 4 bits used to complete the bit string representing the message.
Fill bits: used to fill empty bitstream positions.

Fig. 19. A bitstream containing data codewords.

ECC code words (error-correcting code) are added to a sequence of data code words to detect and correct data code words in case of errors or erasures. These are Reed-Solomon codes created from data code words. We'll talk a little more about them in step 7.

The number of data codes and error correction codes (ECC) depends on the version and level of error correction. They are divided into groups (1 or 2) and into blocks (from 1 to 67) depending on the version and level of error correction.

Fig. 20. Error Correction Characteristics for Version 6 (p. 35 of the ISO standard)

In our case (version 6, H level) we will have 15 data code words and 28 ECC code words for each block. The QR code will contain 1 group of 4 blocks for a total of 172 code words.

Fig. 21. Blocks of data codes. Each Codeword has a length of 8 bits. They carry part of the bitstream from Figure 19.

Figure 22. ECC Codewords blocks. They are 8-bit Reed-Solomon codes obtained from data blocks.

6. QR code decoding

The next step was to read the QR code and fill out as many tables of data code words and ECC from step 5.

The first step was to unmask (unmask) a QR code. We used the Google spreadsheet to create a mask and used the BITXOR function to apply it.

Figure 23. When applied to the QR code, each green mask module inverts the color of the module.

The result of the masking process is a readable QR code. How to read a QR code and where to start? The ISO standard explains how code words are mapped to a QR code and how to read them (p. 46: Placing a code word in a matrix).

Let's put code words on a QR code.

Figure 24. Position of data codewords and error correction codes. You can see regular and irregular characters.

Now let's read each of them. Each character must be read differently depending on its shape and reading direction, as shown below, and as described on page 47 of the ISO standard.

Figure 25.

Below is a readable QR code, where every X is an unknown bit.

Figure 26. Manual decoding, one bit at a time. It looks funny, right?

We then read and populated the data tables and ECC from step 4.

Fig. 27. Data code words after we read the QR code, filled in the protocol bits and those that we obtained using image analysis.

The code words # 1 and # 2 are known, since they are part of the protocol (mode indicator + number of characters indicator).

The code words 3, 4, 6 and 7 are known based on the image analysis that we did in step 2 (“KyUzsR”)

Code words No. 54 to No. 60 are also known, since they are part of the protocol (Terminator + Padding bits).

Each open "X" increases our chances of success in the ECC phase and divides by 2 the number of opportunities that we will have to overcome in the future.

You may be wondering why the entire 5th bit of all codewords carrying the message / data is set to “0”. This is because we know the alphabet of the private key ( Base58Check ), and all the characters in this alphabet begin with "0" when encoding to 8 bits. (The 5th bit in each codeword is the first bit of each letter of the message due to the shift introduced by the bits of the first 12th protocol).

Fig. 28. Table of ECC code words after we read the QR code. Here we can do nothing, since all of them are determined by the Reed-Solomon decoder.

Let's now use the magic of the error correction code to recover as much data as possible.

7. Error Correction Code

At this stage, we were still far from the full key value, but soon we were able to find out if we collected enough data to recover the key using ECC.

ECC (Error Correction Code) is a technology that provides reliable communication over unreliable channels. It can restore the original data, detecting and correcting errors and erasing.

QR codes implement Reed-Solomon codes (a subtype of the BCH code, which we saw when decoding a format information line in step 3).

We will not explain in detail how to encode or decode Reed-Solomon codes. There are many good resources on the Internet, but in short:

The Reed-Solomon coding device generates the ECC code words. They are the remainder of the division between the polynomial representing the message and the irreducible generator polynomial.

Figure 29. Irreducible generator polynomial for 28 EC code words

The Reed-Solomon decoder is a bit more complicated, because there are many ways to decode a message. For this task there are various decoding algorithms, this page is very useful for understanding the decoding process.

The Reed-Solomon decoder can simultaneously decode erase and error. Unfortunately, there is a limit called Singleton Bound .

The risk that we had had to exceed this limit. Reed-Solomon is an optimal FEC and “vulnerable” to the cliff effect . This means that if you exceed the limit, you cannot get anything from the EU codes, and this is where we needed to resort to brute force.

The limit (number of corrections and error corrections) is determined by the formula below, as defined on page 33 of the ISO standard:

e + 2 * t ≤ d - p

Where:

e: number of corrections
t: number of errors
d: number of error correcting words
p: number of code words for protection against incorrect coding (0 in our case: 6-H)

This formula means that you can correct up to 14 errors or 28 erasures per block (or their combination, if the sum does not exceed 28). We used the fact that we knew where the erasures on the QR code were, in order to have the highest level of error correction (28 code words per block).

Let's check each block if we are below or above the limit:

Block 1: data contains 6 erasures, ECC contains 22 erasures
Block 2: data contains 12 erase, ECC contains 21 erase
Block 3: data contains 10 erase, ECC contains 18 erase
Block 4: data contains 6 erasures, ECC contains 21 erasures

With 28 erasures, block 3 and block 1 are at the limit, and can be restored to 100%. The same for block 4, total 27 erasures.

With 33 erasures, block 2 is above the limit, and we will have to resort to brute force. Fortunately, brute force will be made on a small number of combinations.

8. Python and brute force

We decided to use the Python Reed-Solomon codec to decode the message.

We will use a combination of Python code and pseudocode to describe the steps we have taken to find the final result.

Let's start with the best scenario when we are below the limit and decode block 3, 4 and 1.

Figure 30. Decoding unit 3 using a Reed-Solomon decoder.

Decoding result of the 3rd block:

[115, 22, 181, 6, 151, 103, 118, 229, 22, 133, 167, 39, 101, 164, 87]

The same process for block 4, just change the values of the variables mess, ecc and error_pos. Result:

[118, 132, 183, 38, 36, 99, 116, 53, 96, 236, 17, 236, 17, 236, 17]

Block 1 decoding result:

[67, 68, 183, 149, 87, 167, 53, 39, 86, 71, 4, 230, 180, 196, 182]

So far, so good. Unfortunately, if we try to do the same with block 2, the decoding will fail because we will increase the limit.

The only solution we had was brute force. We had a negative margin of 5 (33 erase instead of 28), so the goal was to restore (brute-force) 5 code words and see what result decryption gave us.

To reduce the amount of potential, we looked at tables 27 and 28 for bytes with fewer unknown bits. Interesting were the code words 17, 19, 20, 27 and the EC code word 50.

21 unknown bits add up to 2²¹ (2,097,152) combinations. Not so much. Below is the brute force pseudocode.

Figure 31. The brute force of the second block gives us the last bits needed.

My i5-6600K processor was able to calculate about 30,000 keys per minute on a single core. It took 30 minutes and 838,849 samples to find the first solution that was suitable for recovering the secret key (of these 2,097,152 combinations, there were only 2 solutions that matched the filters).

Figure 32. Bruteforce block 2.

Result for the second block:

[85, 99, 35, 131, 19, 84, 181, 99, 148, 87, 165, 38, 99, 116, 84]

Now we have all the code words, the last step is to convert all these code words to binary, fill in table 27, trim the first 12 bits, the last 52 bits, decode and voila!

The end result is a secret key:

KyUzsRudpNkLKeV2815KV9EzRf7EG1kPivwnQhZrvZEwhKrbF7CV

It goes without saying that you should not use this secret key, since it is no longer relevant!

QR code of the secret key is restored.

Roger, thank you for the sale. The BCH redemption process was not as simple as scanning a QR code on TV, but it was difficult and fun.

Translation: Vyacheslav Bukatov

The translation was carried out with the support of the company EDISON Software , which professionally develops accounting systems for enterprises, for example, accounting of production and sales of typographic products and accounting of pool visits .

Source: https://habr.com/ru/post/341212/

All Articles