Hacking Bitcoin on TV: obfuscate, don’t obfuscate, we’ll still get a QR

Original author: Michel Sassano
  • Transfer

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


image

We could simply call this post “How Good is the QR Code and How We Recover It from Almost Anything.” But it is much more interesting when the QR code is the key to the wallet in the amount of $ 1000 in cue ball.



Part of the documentary 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 Ver. Anyone who had access to this video could get a secret key.

Bitcoin, Ethereum, Litecoin, Dash, Neo ...
Cryptocurrencies are everywhere and are developing rapidly. As for me, I have been watching bitcoin since 2013 (but that does not mean that I buy). I had to read Mastering Bitcoin 3 times to understand how each part of it really works and to be able to explain it to others. Nevertheless, I can not keep up with the modern market, new cryptocurrencies, algorithms, new ICO everywhere appear every day.

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

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

The main 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. Everything is simple.

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

Introduction


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

image


image

Figure 1. Difficult QR code and secret key.

I saw several people complaining about it 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 pin Bitcoins, but because it was legally bound.

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 blur.

The story could end at this point, $ 1000 would be lost forever, as I do not think Roger Werth kept a copy of the secret key. Only the interviewers could buy back the bitcoins.

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

image

Fig 2. The open part of the QR code and the smeared line with the key below.

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

To be honest, the chances of finding a secret key using only brute force were close to zero. We knew the properties of QR codes and their resistance to damage. Our goal was to collect as much information as possible, in order to reduce the number of unknown parameters to a minimum. We knew that at some step, we would 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, all the steps we took to get the secret key.

  1. Collection of information
  2. Let's shaman. Image processing.
  3. QR Code Standard, Part 1
  4. QR code reconstruction
  5. QR Code Standard, Part 2
  6. QR code decoding
  7. Error correction code
  8. Python Brute

1. Collection of information


The first step was to collect as much information as possible from the interview. We watched the playback frame by frame and got some shots, such as: The

public key, which leads us to the (almost) empty BTC wallet . Roger Ver lied? Many people talked about this on Twitter. He didn’t lie, he posted on his twitter post where he talked about the sale . We had to look for a BCH wallet .

image

Figure 3. Public key and QR code: 17Qgadvc7pm51mV9r9zUAs4xU1XXwDRr8o

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

image

Fig 4. The overlooked part of the string with the secret key. You can see 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.

image

Figure 5. The last letter is clearly distinguishable V.

Screenshots of poor quality above and below the QR code. They will also be useful to get (a little) more data and fill out a QR code during the recovery phase.

image

Fig 6. The upper part of the QR code, the first line can be used.

image

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

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

KwjiU4CVAmdyxyDbvkbx2XbSoU1nxZgyXz7usqAemvsd4RdGHoPF


The next step is to recreate the QR code.

2. Let's be a shaman. 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 the obtained screenshots?

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

The second screenshot we wanted to work on had a small part of the private key. We knew that we needed to have at least a small amount of data if we want the ECC (Error Correction Code) code 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 it because this guy conducted some tests on QR codes, and in the comments confirmed that they are scanned

image

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

Two unclear versions of the private key string. The first gives us the first four letters (we obviously don’t see “K”), and the second gives us the first six letters (we don’t see “z”).

image

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

image

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

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

3. QR Code Standard, Part 1


It was important to understand how QR codes work and the limitations of their ECC capabilities in recovering 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.

image

Figure 11. Error Correction Level and 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.

image

Fig 12.

An interesting blue column for us was (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 in (x: 8, y: 22-28) are bits 8-14 of the line. We had only 7 bits out of 15, but that was enough to find the information we needed.

The format information string encodes the error correction level (EC) 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 for 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 .

image

Figure 13.

From top to bottom. We have bits 8 to 14 of the information line. Bit 14 is the most significant. In the screenshot number 11 we can read it.

0011001XXXXXXXXX


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

image

Fig 14.

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

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

The QR code encoding format is an 8-bit Byte type , the numeric and alphanumeric types are not supported by the secret key alphabet (without lowercase letters), Kanji encodes 2 bytes (we only need one), and ECI is iteration .

We were almost ready to begin the reconstruction of the QR code, the last thing we needed to know was 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 maximum capacity based on the encoding format and error correction level.

The capacity of each QR code depends on its version and the error correction level. Details can be found on page 28 of the ISO standard.
We knew that the QR code was supposed to store 52 characters (416 bits) with error correction level H.

image

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

QR code size of the 6th version is 41x41px.

Now we had all the information necessary to begin 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 a Google spreadsheet (where it’s easy to draw and apply features such as masking a QR code).

We have completed the following steps:

  1. Draw each template that is part of the standard (positioning template, alignment template (only one from the QR code version 6), synchronization template, and delimiters, as shown in Figure 12)
  2. Add bits from the format information line found in the previous step.
  3. 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. This is not so much, but at this stage, every bit matters.

image

Figure 16. How we collected a few more bits in the upper lines.

image

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

Below, the QR code that we were able to recover. The next step is to determine the sequence of bits for extracting codewords and error correction codewords.

image

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 wanted to extract more bits from it.

A QR code consists of data code words and error correction code blocks .
Each block is 8 bits long, and each bit is represented by a module (black or white square). You cannot say, simply by looking at the QR code, that the specific white square is “0” or “1”, because, as we will see later, a mask is applied to the QR code before rendering it.

Data code words contain 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.
  • Character Count Indicator: A sequence of bits that indicates the length of a message. Changes in accordance with the encoding mode and version of the QR code.
  • Message / data stream (private key). (8 bits per character)
  • Terminator: 4 bits used to end the bit string representing the message.
  • Fill Bits: Used to fill in empty bitstream positions.

image

Fig. 19. Bitstream containing data code words.

The ECC (error-correcting code) codewords are added to the data codeword sequence to detect and correct the data codewords in the event of errors or deletions. These are Reed-Solomon codes created from data code words. We will 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.

image

Fig. 20. Error correction characteristics for version 6 (p. 35 of the ISO standard)

In our case (version 6, level H) 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.

image

Fig. 21. Blocks of data codes. Each Codeword is 8 bits long. They carry part of the bitstream from Figure 19.

image

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

6. Decoding a QR code


The next step was to read the QR code and fill out as much of the data code word and ECC table as possible from step 5.

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

image

Figure 23. When applied to a 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 codewords are displayed on a QR code and how to read them (p. 46: Placing a codeword in a matrix).

Let's put the code words on the QR code.

image

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 should be read differently depending on its shape and direction of reading, as shown below, and as described on page 47 of the ISO standard.

image

Figure 25.

Below is a bit-by-bit read QR code, where each X is an unknown bit.

image

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

Then we read and populated the data and ECC tables from step 4.

image

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

Code words # 1 and # 2 are known because they are part of the protocol (mode indicator + character number indicator).

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

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

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

You might be wondering why the entire 5th bit of all codewords carrying a message / data is set to “0”. This is because we know the private key alphabet ( Base58Check ), and all characters in this alphabet begin with "0" when encoding for 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).

image

Figure 28. ECC codeword table after we read the QR code. There is nothing we can do here, since they are all 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 point, we were still far from the full value of the key, but soon we could find out if we had collected enough data to restore the key using ECC.

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

QR codes implement Reed-Solomon codes (the subtype of the BCH code that we saw when decoding the format information string in step 3).
We will not explain in detail how to encode or decode Reed-Solomon codes. There are a lot of good resources on the Internet, but in short:

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

image

Figure 29. The irreducible generator polynomial for the 28 EC codewords

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

The Reed-Solomon decoder is capable of simultaneously decoding erasures and errors. Unfortunately, there is a limit called Singleton Bound .

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

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

e + 2 * t ≤ d - p

Where:

  • e: number of fixes
  • t: number of errors
  • d: number of error correction codewords
  • p: number of codewords to protect against incorrect encoding (0 in our case: 6-H)

This formula means that you can correct up to 14 errors or 28 erasures per block (or a combination of them if the amount does not exceed 28). We used the fact that we knew where the erasures were on the QR code 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 erasures, ECC contains 21 erasures
  • Block 3: data contains 10 erasures, ECC contains 18 erasures
  • 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, a total of 27 erasures.

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

8. Python and brute force


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

We will use a combination of Python code and pseudocode to describe the steps we took 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.

image

Figure 30. Decoding block 3 using the 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 value of the variables mess, ecc and error_pos. Result:
[118, 132, 183, 38, 36, 99, 116, 53, 96, 236, 17, 236, 17, 236, 17]

Decoding result of block 1:
[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, decoding will fail because we will use the limit.

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

To reduce the potential, we looked in tables 27 and 28 for bytes with fewer unknown bits. The codewords 17, 19, 20, 27 and the EC codeword 50 were interesting.

21 unknown bits in total give 2²¹ (2 097 152) combinations. Not so much. Below is the brute force pseudo-code.

image

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

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 restoring the secret key (out of these 2,097,152 combinations there were only 2 solutions that matched the filters).

image

Figure 32. Bruteforce of 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, 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, as it is no longer relevant!

image

The secret key QR code has been 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 supported by EDISON Software , a company that professionally develops accounting systems for enterprises, for example, accounting for the production and sale of printing products and accounting for pool visits .

Read more



Also popular now: