Homework 3

h3 Public key encryption and PGP

Task a: Read and summarize (with 1-5 bullet points for each heading)

Schneier 2015: Applied Cryptography Chapter 1: Foundations €

TERMINOLOGY

• “A cryptographic algorithm, also called a cipher, is the mathematical function used for encryption and decryption. (Generally, there are two related functions: one for encryption and the other for decryption.)” (Schneier 2015)
• The difference between symmetric and asymmetric encryption is that symmetric encryption uses the same key for both encryption and decryption, while asymmetric encryption uses two different keys for both procedures.

• “Cryptanalysis is the science of recovering the plaintext of a message without access to the key. Successful cryptanalysis may recover the plaintext or the key.” (Schneier 2015) “An attempted cryptanalysis is called an attack.” (Schneier 2015)
• A closed encryption algorithm is not a guarantee that it is reliable. The best encryption algorithms we have are the ones that have been made public, because they have been attacked by the world’s best cryptographers for years, and are still unbreakable.
• “An algorithm is unconditionally secure if, no matter how much ciphertext a cryptanalyst has, there is not enough information to recover the plaintext.” (Schneier 2015)
• “Pronouncing an algorithm secure simply because it is infeasible to break, given current technology, is dicey at best. Good cryptosystems are designed to be infeasible to break with the computing power that is expected to evolve many years in the future.” (Schneier 2015)

STEGANOGRAPHY

• “Steganography serves to hide secret messages in other messages, such that the secret’s very existence is concealed. Generally the sender writes an innocuous message and then conceals a secret message on the same piece of paper.” (Schneier 2015)

SUBSTITUTION CIPHERS AND TRANSPOSITION CIPHERS

• “Different cryptographic algorithms either substituted characters for one another or transposed characters with one another. The better algorithms did both, many times each.” (Schneier 2015)
• “These days in computer era, algorithms work on bits instead of characters. This is actually just a change in the alphabet size: from 26 elements to two elements. Most good cryptographic algorithms still combine elements of substitution and transposition.” (Schneier 2015)
• “A substitution cipher is one in which each character in the plaintext is substituted for another character in the ciphertext. The receiver inverts the substitution on the ciphertext to recover the plaintext.” (Schneier 2015)
• “In a transposition cipher the plaintext remains the same, but the order of characters is shuffled around.”  (Schneier 2015)

SIMPLE XOR

• “XOR is exclusive-or operation: ‘^’ in C or ⊕ in mathematical notation. It’s a standard operation on bits:
  • 0 ⊕ 0 = 0
  • 0 ⊕ 1 = 1
  • 1 ⊕ 0 = 1
  • 1 ⊕ 1 = 0    ” (Schneier 2015)

• “XOR is a symmetric algorithm. The plaintext is being XORed with a keyword to generate the ciphertext. Since XORing the same value twice restores the original, encryption and decryption use exactly the same program:Р ⊕ К = С
  С ⊕ К = Р ” (Schneier 2015)
• Simple XOR is a very low security encryption method.

ONE-TIME PADS

• “In one-time pad each key letter is used exactly once, for only one message. The sender encrypts the message and then destroys the used pages of the pad or used section of the tape. The receiver has an identical pad and uses each key on the pad, in turn, to decrypt each letter of the ciphertext.” (Schneier 2015)
• “Since every plaintext message is equally possible, there is no way for the cryptanalyst to determine which plaintext message is the correct one. A random key sequence added to a nonrandom plaintext message produces a completely random ciphertext message and no amount of computing power can change that.” (Schneier 2015)
• “Key letters in one-time pad have to be generated randomly. Any attacks against this scheme will be against the method used to generate the key letters.” (Schneier 2015)
• “Messages encrypted using one-time pads are still secure today and will remain that way forever. It doesn’t matter how long the supercomputers work on the problem.” (Schneier 2015)

COMPUTER ALGORITHMS

• Three of the most common cryptographic algorithms are:
  • DES (Data Encryption Standard)
  • RSA (named for its creators—Rivest, Shamir, and Adleman)
  • DSA (Digital Signature Algorithm, used as part of the Digital Signature Standard)

LARGE NUMBERS

 

Source:

Bruce Schneier 2015: Applied Cryptography: Protocols, Algorithms and Source Code in C

 

Task b: Give two examples of public key cryptography (other than PGP). Explain how public keys are used here.

Public key cryptography serves both to authenticate a message and to ensure its confidentiality. How does it work? Well, the most commonly used use case for public key cryptography is network traffic using the HTTPS protocol encrypted with an SSL/TLS certificate.

 

The SSL certificate contains a public key that a browser downloads automatically when a user visits a website that uses the HTTPS protocol. Once the certificate is obtained, all traffic between the browser and the website will be encrypted using the public key from that website’s SSL certificate. The key pair is created by the owner of the website, and only the owner of the private key can decrypt the message encrypted with the public key.

 

But how can we be sure that the site certificate is a real certificate published by the site owner? Well, for this we can ask someone whom everyone trusts to certify the authenticity of the certificate of their digital signature. In a digital signature, asymmetric encryption works differently. A message, or in this case a certificate, signed with the Certificate Authority’s private key can be verified by anyone who knows the public key of the CA. The most commonly used root CA certificates end up in a web browser when you install or update your browser.

 

A certificate can be signed with multiple digital signatures. In this chain, the trusted issuer CA is always at the root level of the chain. For example, the Google.com website is digitally signed with a GTS CA 1C3 certificate signed by a GTS Root R1 certificate signed by the trusted provider GlobalSign Root CA – R1. All certificates in this chain are valid, so we can be sure that encrypted traffic sent to Google.com will only be decrypted by the owner of Google.com’s private key.

 

 

Task c: Encrypt and sign a message. Then decrypt and verify it. Use PGP to encrypt and sign messages.

I am using Kali linux distribution on the VMWare Workstation 15 Pro hypervisor. PGP comes pre-installed with Kali Linux, so I needed to read the pgp help to learn the command syntax.

$ gpg –help
gpg (GnuPG) 2.2.27
libgcrypt 1.9.4
Copyright (C) 2021 Free Software Foundation, Inc.
License GNU GPL-3.0-or-later <https://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Home: /home/kali/.gnupg
Supported algorithms:
Pubkey: RSA, ELG, DSA, ECDH, ECDSA, EDDSA
Cipher: IDEA, 3DES, CAST5, BLOWFISH, AES, AES192, AES256, TWOFISH,
CAMELLIA128, CAMELLIA192, CAMELLIA256
Hash: SHA1, RIPEMD160, SHA256, SHA384, SHA512, SHA224
Compression: Uncompressed, ZIP, ZLIB, BZIP2

Syntax: gpg [options] [files]
Sign, check, encrypt or decrypt
Default operation depends on the input data

Commands:

…

 

In order to encrypt something, I needed to first generate a key pair using gpg command with option –gen-key . The wizard asked for my real name and email address.

$ gpg –gen-key
gpg (GnuPG) 2.2.27; Copyright (C) 2021 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Note: Use “gpg –full-generate-key” for a full featured key generation dialog.

GnuPG needs to construct a user ID to identify your key.

Real name: Aleksandr Pantsesnyi
You selected this USER-ID:
“Aleksandr Pantsesnyi <aleksandr.pantsesnyi@myy.haaga-helia.fi>”

Change (N)ame, (E)mail, or (O)kay/(Q)uit? o
We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.
We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.

…

Then I had to enter a passphrase.

I listed all existing keys using gpg –list-keys command

I created a test file using the nano editor

$ nano test-file.txt

After typing some text in the editor, I saved it with the Ctrl+X hotkeys, confirmed that I’m sure using the letter Y, and enter. After that, using the cat command, I checked the contents of the file.

Encryption

I then encrypted the test file using the -r (recipient) option and the –encrypt option with the filename. GPG has created a new file with a .gpg extension at the end of the name. This is an encrypted file whose content is encrypted and cannot be read by a human in the cat command.

Decryption

I then decrypted the encrypted file using gpg with the -d option and the filename. GPG asked me to enter the passphrase for the private key, after which the text of the file appeared on the screen in text format.

Signing

I signed the file using gpg with the –sign option and the filename. GPG created a new .gpg file that looked larger than just the encrypted file.

I checked the size of both files using the du command with the -b (bytes) flag. Adding the signature increased the file size by several hundred bytes.

Verifying

Using gpg with the –verify option and a filename, I got the file is really signed by me today using an RSA key, and the signature is good.

 

In the case of asymmetric encryption and digital signature, the same pair of public and private keys was used. In the case of encryption, it was done with a public key and decryption with a private key. In the case of a signature, a private key was used and the authenticity of the signature was verified with a public key.

 

Source: https://linuxhint.com/encrypt-decrypt-with-pgp/

 

Task f: Voluntary, programmers only: Cryptopals. Solve Set 1: Challenges 1-3. I highly recommend Cryptopals for learning to break cryptography.

Challenge 1: Convert hex to base64

I chose the Python language and Jupyter notebooks. After some googling, I figured out that I need to use the base64 library to accomplish this task. Using the b64encode method, I encoded and decoded a bytes string extracted from the HEX string. Then, using the b64decode method, I decoded the result back into a HEX string and compared that the decoded result equals the original HEX string.

Challenge 2: Fixed XOR

So, I had to write a simple function using Python language and Jupyter notebook. The function takes two arguments and returns the result as a byte string. Because the function must take two buffers of the same length, I added an assertion to compare the string lengths. Then, using a for loop, the function goes through each pair of bytes from both inputs and XORs that pair. The result of each XOR will be added to the result array using the append function.

Because the input strings are in the form of a HEX string, I had to first convert them to a byte type. I then called the function and gave the input strings as arguments. The result is printed as byte string and as HEX string also.

Challenge 3: Single-byte XOR cipher

In this task, I needed to find one character with a length of one byte. This means that I had to create a FOR loop in which I would iterate over all 256 options that can take a byte. On each iteration, I XORed the input string by byte value. So, I had 256 output options, from which I had to extract the best option in human-readable English. Typically, text is written using mostly lowercase letters and spaces between words. So the range of lowercase ASCII letters is 97-122, and the space character is 32. I created a list with all of these values, and on each iteration I compared the results for the highest match against the values in that list. The function returns a list of results that contains three values: the best match key, the most English letters, and the best match plain text.

I then passed a HEX encoded string to the variable and called a function that passed that variable as an argument. The returned result has been printed below.

Sources:

https://cedricvanrompay.gitlab.io/cryptopals/challenges/01-to-08.html

ASCII table : https://www.cs.cmu.edu/~pattis/15-1XX/common/handouts/ascii.html