Block Ciphers

Disclaimer: These posts help mostly myself to assimilate what I’m learning about cryptography and should not be taken as a final word or academic truth. I encourage you to correct me if you find that I’m wrong.

So as I promised here is my entry on what I’ve learned lately about Block Ciphers and their mode of operation. Basically a Block ciphers allows us to encrypt a block of n bits of data data, there are many block cipher implementations, among the most popular ones are DES ( now deprecated) 3DES, AES.

AES particularly operates on blocks of 16 bytes ( 128 bits) with keys ranging from 128 to 256 bits. Therefore we need additional constructs to actually make the block cipher useful for larger pieces of data, there are several modes of operation of block ciphers and among the most popular ones there are CBC (Cipher Block Chained) and CTR or Counter mode. CBC basically works by creating a random Initialization Vector (IV) of 16 bytes and XORing it against a block of the same length on the plain text message, then it uses AES to Cypher the result with a chosen key. Subsequently we use the output of this output and XOR it against the next block of the plain text message. Best explained by this diagram: example 1431810452_601px-CBC_decryption.svg.png example 1431810440_Cbc_encryption.png

The IV is usually prepended to the message and it’s retrieved when needed for decryption which is basically the same process but using the AES decryption algorithm first and then XOR it against the IV. Then we feed the next iteration using the cipher text from the previous step.

example 1431810511_Ctr_encryption.png example 1431810516_Ctr_decryption.png

There is also another mode of operation which is Counter mode, which instead of relying on the output of the encryption algorithm to cipher the next chunk of plain text it just appends or adds a unit to the Initialization Vector and XORs it with the plain text. It’s worth mentioning that while on CBC we need to perform an AES decryption to retrieve the message, in CTR mode we will actually perform the encryption in both ways. What is interesting about CTR is that since we can easily calculate IV + 1 without needing any other additional processing we can make this process concurrent, and that’s what makes it an interesting algorithm to implement with go.

Preparing:

In order to implement the algorithm we will use some libraries, and we will build some functions of our own, first is the aes package in the golang library. Then a convenience XOR function defined as:

package tools

// XORS 2 []byte
func XOR(a, b []byte) []byte {
    var result []byte = make([]byte, len(a))
    for i := 0; i < len(a); i++ {
        result[i] = a[i] ^ b[i]
    }
    return result
}

The function is pretty straightforward, it takes two bytes as parameters and performs a bitwise XOR on each one, it will fail if the arrays are of different sizes, but since we’re supposed to work with 16 bytes it shouldn’t matter.

We’d define the CTR struct with a factory method to set the key

package ctr

import (
    "bytes"
    "crypto/aes"
    "crypto/cipher"
    "crypto/rand"
    "github.com/juanfgs/hmwk_crypto/tools"

)

type CTR struct {
    Cipher cipher.Block
}

func New(key []byte) CTR {
    cipher, err := aes.NewCipher(key)
    if err != nil {
        panic(err)
    }
    return CTR{cipher}
}

and some convenience methods to cipher each block with AES:

func (this CTR) EncryptBlock(ct []byte) []byte {
    var pt []byte = make([]byte, aes.BlockSize)
    this.Cipher.Encrypt(pt, ct)

    return pt
}

This one is just for having a better legibility

func GrabBlock(full []byte, blockSize int, index int) []byte {
    return full[index : index+blockSize]
}

Then we implement the Encrypt method as follows:

func (this CTR) Encrypt(pt []byte) []byte {
    var iv []byte = make([]byte, aes.BlockSize) 
    _, err := rand.Read(iv) // We generate a random IV of 16 bytes

    if err != nil {
        panic(err)
    }
    CT := append([]byte{},iv...) // we append the IV to the cipher text, 

    max := len(pt) / aes.BlockSize  // we determine the maximum blocks of 16 bytes we can get from the plain text
    rest := len(pt) % aes.BlockSize  // we determine the length of the remaining bytes to get from the plaintext
    CTChan := make(chan []byte, max +1)  // we define a channel to send our CT blocks, of size max +1 to store all the bytes
    IVChan := make(chan byte, max +1) // we define a channel to send our modified IV 
    for i := 0; i <= max; i++ {

        var blockSize int 

        if i == max {
            blockSize = rest
        } else {
            blockSize = aes.BlockSize
        }

        block := GrabBlock(pt, blockSize, i * aes.BlockSize) // we grab a block from the plaintext

        go func( Block []byte) {

            CTChan <- tools.XOR(Block, this.EncryptBlock(iv)) //we cipher it against the iv and send it back to the CT channel
            IVChan <- iv[len(iv)-1] + 1 // we send the increased counter through the IV channel

        }( block )

        iv[len(iv)-1] = <- IVChan  // we receive and effectively increase the counter

    }
    go func(){
        close(CTChan)  // we close the ct channel
    }()


    for val := range CTChan{
        CT = append(CT,val...) // we append the values from the channel to the final CT
    }

    
    return bytes.TrimSuffix(CT, []byte{0}) // we remove any zeroed bytes at the end of the CT

}

The decryption method is pretty similar:

func (this CTR) Decrypt(ct []byte) []byte {
    var PT []byte
    iv := ct[:aes.BlockSize]  // we extract the IV from the beginning of the CT 

    CT := ct[aes.BlockSize:] // we slice the actual CT for convenience


    max := len(CT) / aes.BlockSize
    rest := len(CT) % aes.BlockSize
    PTChan := make(chan []byte, max +1)
    IVChan := make(chan byte, max +1)
// this code does pretty much the same

    for i := 0; i <= max; i++ {
        var blockSize int

        if i == max {
            blockSize = rest
        } else {
            blockSize = aes.BlockSize
        }

        block := GrabBlock(CT, blockSize, i * aes.BlockSize) // now we grab blocks from the CT instead of PT
        go func( Block []byte) {

            PTChan <- tools.XOR(Block, this.EncryptBlock(iv))  // we ENCRYPT (not decrypt) the iv and send the XOR back
            IVChan <- iv[len(iv)-1] + 1

        }( block )
        
        iv[len(iv)-1] = <- IVChan

    }
    
    go func(){
        close(PTChan)
    }()


    for val := range PTChan{
        PT = append(PT,val...)
    }

    return PT
}

And voilá, basically we have our CTR encryption system ready, you can find the full code and a partial CBC implementation on this github repo.

This was a very exciting thing to do and I learned a lot about cypto, golang channels and more. I hope you liked it!

  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket