XOR encryption and perfect secrecy

  • BitKey
  • 7 Minutes
  • June 2, 2018

Keyword: Security backup, XOR encryption, perfect secrecy

1. Introduction.

XOR is short for exclusive-OR operation. XOR is one of the basic binary operations like AND, OR, NOT operation.

img

Figure: The Vernam Cipher Using XOR operation.      

The XOR (exclusive-OR) operation acts as that the output is 1, if the inputs are different, but 0, if the inputs are the same.

Exclusive-OR operation table:

1
2
3
4
5
6
INPUT  INPUT      OUTPUT
A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0

2. XOR encryption and perfect secrecy

XOR encryption use exclusive-OR operation to encrypt data:

1
message  XOR  password  =   cipherText

For example, the string “abc” (01100001 01100010 01100011 in 8-bit ASCII) can be encrypted with the password “key” (01101011 01100101 01111001) as follows:

1
2
3
4
        01100001 01100010 01100011              //"abc"
XOR 01101011 01100101 01111001 //"key"
_______________________________________
00001010 00000111 00011010 //cipherText

XOR encryption is symmetric encryption, the decryption progress:

1
password  XOR cipherText =  message

For example:

1
2
3
4
        00001010 00000111 00011010              //cipherText
XOR 01101011 01100101 01111001 //"key"
______________________________________
01100001 01100010 01100011 //"abc"

Generally speaking, XOR encryption as an encryption method is not recommended. The XOR encryption is basically a very simple cipher and easily broken, such as Known-Plaintext Attack. If you repeat use a short password to encrypt a long plain-text message, this won’t stand up minutes before being cracked.

However, coupled with the Mauborgne Constraint: (1) you may never reuse a key, (2) it must be the same size as the plain-text, (3) and it must be from a true random bit source—you have unbreakable cryptography.[1]

this works like an OTP (One-time pad) and Shannon proved that the OTP provided perfect secrecy.[2]

3. Use XOR encryption to protect private-keys

How can we use XOR encryption as an advanced technology to bring perfect-secrecy and unbreakable cryptography to our Bitcoin wallet?

Before we answer this question, let’s first ask why we do not just use an advanced and mature encryption method like AES to protect our wallet data.

AES encryption is an industry-recommended advanced encryption method and is also widely used in cryptocurrency wallets. There is no clear evidence show that this encryption method has weaknesses or back-doors, however, there may be risks in actual deployment. The risk is main caused by user’s week password. Users often use weak passwords. Even if some software using salt to improve password entropy, but the salt and algorithms can be cracked by reversing engineering.

So AES encryption cannot provide solid security, if the AES encrypted data obtained by an attacker, there is a height risk of being brute-force cracked.

Now we can use a random NFC-XOR-KEY stored in an NFC tag to protect Bitcoin private-keys with perfect secrecy.

And we can meet these two constraints easily:

  1. The XOR-key is random.
  2. The XOR-key is longer than Bitcoin private key length.

but what about the third constraint “you may never reuse a key”?

Review the encrypt progress:

bitcoin_private_key XOR  NFC-XOR-KEY =  xor-encrypted-data

and XOR is commutative, so:

NFC-XOR-KEY XOR bitcoin_private_key =  xor-encrypted-data

Now we look as using the bitcoin_private_key to encrypt the NFC-XOR-KEY, and we know the bitcoin_private_key is random, and there is just one NFC-XOR-KEY as the pant-text message, so the xor-ed key (bitcoin_private_key) is never reused.

So finally, we can use one NFC-XOR-KEY, to protect many Bitcoin private-keys and keep perfect secrecy.

With this perfect secrecy XORed encryption, the protected private keys can resist any brute-force crack. Even if the attacker gets wallet data, he cannot decrypt the private-keys.

4. References

[1] Wolfgang Richter, Unbreakable Cryptography in 5 Minutes. acm.org
[2] Stackexchange, Simply what does “perfect secrecy” mean. stackexchange
[3] One-time pad. wikipedia