Hey ps Gopher! Do you want some privacy? Steganography for Masha and Vitya

I once read an article on how to hide a photo in another photo, here is its translation. The article is rather short and the idea described in it does not carry any novelty. And it was not its simplicity that attracted me to the described idea, but rather a wide range of possible extensions.

I briefly outline the essence of the idea: in one photo (PNG) you can embed another photo or not a photo at all, but whatever you want. The implementation is simple: each least significant bit in the RGB matrix carries a payload, putting them together, you get the byte array that you wanted to hide, and the change in the original image is not perceptible to the human eye. For those who are interested, check out the original article, but in this article we will try to consider possible use cases and improvements.

The implementation is made in the GO language and is available on my github. There you will also find an instruction manual with examples of starting with different keys. And in the folder demo a working demo (however, the application will still have to be compiled first). But, if you are too lazy to compile, then it does not matter, for the lazy, I published the application as a web service. On the this page you can try to hide the encrypted message in your PNG and decrypt it.

So, now about the improvements of the original idea. In order to make it more interesting to read, I will give examples of the use of this application by two secret agents located in different countries. They try to send secure messages to each other over open communication channels. And we will help them with this. Well, for those who are impatient, I will immediately say that the buns are like this:

1. AES encryption;
2. XOR with a key equal to the length of the message;
3. Digital signature.

Nibbles

But first, let’s figure out how to unhook one bit from the original byte array and hide in each byte of each RGB vector in the image?

The concept itself is simple and straightforward: we take the first bit, hide the first RGB vector in R, take the second bit, hide the first RGB vector in G, and so on. In the figure, we see – in the upper part there is an array of data that we want to hide, and in the lower part – the RGB parts of the image. We replace each least significant bit with a bit of data and don’t worry – the changes are so insignificant that you can’t tell the difference with the eye. I didn’t draw the alpha channel intentionally – we don’t hide anything in it, because it’s pale yellow =).

To implement the idea, we “sawing” the initial data on nibbles three bits each. Each nibble will fall entirely on the RGB vector. Thus, in R we will replace the least significant bit with nibble & 1in G we replace the least significant bit by nibble & 2and in B we replace the least significant bit by nibble&4. Leave the alpha channel unchanged.

package nibbles

type nibble struct {
  mask    int16
  size    int
  current int
  data    []byte
}

const (
  MaxNibbleSize     = 6
  MinNibbleSize     = 1
  DefaultNibbleSize = 4
  bitsInByte        = 8
)

func New(size int, data []byte) *nibble {
  var mask int16
  if size < MinNibbleSize || size > MaxNibbleSize {
     size = DefaultNibbleSize
  }
  for i := 0; i < size; i++ {
     mask |= 1 << i
  }
  return &nibble{
     mask: mask,
     size: size,
     data: data,
  }
}

func (n *nibble) Next() (byte, bool) {
  byteIndex := (n.current * n.size) / bitsInByte
  if byteIndex >= len(n.data) {
     return 0, false
  }
  bitIndex := (n.current * n.size) % bitsInByte
  n.current++
  word := int16(n.data[byteIndex])
  if len(n.data) > byteIndex+1 && bitIndex > bitsInByte-n.size {
     word |= int16(n.data[byteIndex+1]) << bitsInByte
  }
  result := (word >> bitIndex) & n.mask
  return byte(result), true
}

func Convert(data []byte, size int) (result []byte) {
  var (
     filledBits int
     bitBuffer  int16
  )
  for _, b := range data {
     bitBuffer |= int16(b) << filledBits
     filledBits += size
     if filledBits >= bitsInByte {
        result = append(result, byte(bitBuffer&0xff))
        bitBuffer = bitBuffer >> bitsInByte
        filledBits -= bitsInByte
     }
  }
  if filledBits >= size {
     result = append(result, byte(bitBuffer&0xff))
  }
  return
}

The final file is saved as a PNG image. And now that everything is ready to implement the main idea, let’s start improving and we will start from the needs that arise during the operation.

AES encryption

Agent Masha wants to send a message to agent Vitya. She agrees with her friend (who lives in another country) that on a certain day and a certain hour she will post a photo on the network with a message hidden inside. But there is a problem: the agents listening to it learn about this move and receive the file, parse it and restore the original message. Why shouldn’t she encrypt the message?

Let’s help them out and add some AES symmetric encryption. In GO, encryption with this algorithm is implemented by the package crypto/aes. It is enough to simply create an encryption block by calling the function aes.NewCipher(key). And now we can cut the data into blocks and apply the method to each of them Encrypt.

As you can see, the payload is encrypted block by block, and if we try to encrypt a photo, it may turn out that the outlines on the encrypted picture still remain, although the colors are lost. So, to increase cryptographic strength, we will apply the propagating block chaining mode – this is when the first block is encrypted with our key, and the ciphertext obtained in the previous step is mixed into each subsequent block. About AES synchronous ciphers, you can read here.

Masha and Vitya must agree on the keys in advance: when they meet in person, they need to exchange several keys, one main and several backup ones in case the main one is compromised. It is very important that these keys do not leak into the public network!

func EncryptDataAES(data []byte, key []byte) ([]byte, error) {
  aesEncoder, err := newAES(key)
  if err != nil {
     return nil, err
  }
  chainSize := aesEncoder.blockSize()
  // первым блоком будет блок информации о размере исходного сообщения
  // т.к. мы собираемся выровнять его по chainSize
  infoBlock := newSizeInfoChunk(len(data), chainSize)
  data = alignDataBy(data, chainSize)
  encrypted := make([]byte, len(infoBlock)+len(data))
  // шифруем блок с информацией
  if err = aesEncoder.encode(encrypted[0:len(infoBlock)], infoBlock); err != nil {
     return nil, err
  }
  // шифруем все сообщение
  for n := 0; n < len(data)/chainSize; n++ {
     var dst, src = encrypted[(n+1)*chainSize : (n+2)*chainSize], data[n*chainSize : (n+1)*chainSize]
     if err = aesEncoder.encode(dst, src); err != nil {
        return nil, err
     }
  }
  return encrypted, nil
}

type encoder struct {
  cipher cipher.Block
  initVc []byte
}

func newAES(key []byte) (*encoder, error) {
  block, err := aes.NewCipher(key)
  if err != nil {
     return nil, err
  }
  enc := encoder{
     cipher: block,
     initVc: make([]byte, block.BlockSize()),
  }
  return &enc, nil
}

func (e *encoder) blockSize() int {
. . .

func (e *encoder) encode(dst, src []byte) (err error) {
. . .

func (e *encoder) decode(dst, src []byte) (err error) {
. . .

The length of the key is equal to the length of the message

The AES cipher is a good thing, but they say that the most cryptographically strong key is a key equal in length to the original message. Listening agents can parse enough messages to derive the key from the first block (which is not mixed in with ciphertext).
Masha and Vitya are not stupid, they use double encryption: immediately after the message is encrypted with the AES algorithm, they apply a simple XOR with a key equal to the original message. We are adding this feature to our application: the key will be some other photo (or any file) that can also be transferred through public channels. Masha attaches the date and time of the next transmission of such a key to each message. It is very important to use a new key for each subsequent message. If the listening agents could not decrypt the message, the key will change every next time, which makes cryptanalysis difficult.

Now a little about entropy. No brainer that we need to use “random data” as a key, and our logic describes the use of an image that may contain low entropy. It’s okay, we will add a function to the algorithm of our program moreStrongKey(key []byte) []byte which will “knead” the bits in the file so that they look like random ones. The function is scalar and, when executed on the same file, produces the same jumbled data array.

func EncryptDecryptData(data []byte, key []byte) error {
  key = moreStrongKey(key)
  if len(key) < len(data) {
     return ErrKeyShortedThanData
  }
  for i, d := range data {
     data[i] = d ^ key[i]
  }
  return nil
}

func moreStrongKey(key []byte) []byte {
	const (
		salt   = 170
		bufLen = 16
	)
	var (
		buf [bufLen * 2]byte
		unf int
		out []byte
	)
	flush := func() {
		unf = 0
		h := md5.Sum(buf[:])
		out = append(out, h[:]...)
	}
	for i, b := range key {
		r := key[len(key)-i-1]
		p := i % bufLen
		buf[p*2] = b
		buf[p*2+1] = b ^ r ^ salt
		unf++
		if (i+1)%bufLen == 0 {
			flush()
		}
	}
	if unf > 0 {
		flush()
	}
	return out
}

Masha and Vitya encrypt their messages in two cascades, changing the XOR key with each new message. And we’re pretty sure no one is eavesdropping on them. But there is one more case when all the applied tricks will not be enough.

Digital signature

Now about the bad: Masha was covered. AES keys ended up in the hands of attackers, and with the help of them it was possible to decrypt some messages! But at the last moment she managed to escape and now she must tell Vita that this is a failure.
“Do not trust anyone” she writes in the last message and posts it at the agreed time. But here’s the problem. Now attackers, using the keys, can post their message and completely capture their communication channel. How can she prove that her message is true?

Let’s add to our code the ability to digitally sign a message using asynchronous keys? Right here you can learn a little about digital signatures. We use RSA keys and will teach our application to generate such keys, although our own will do.

It’s very good that Masha keeps the encryption keys separate from the signing keys in her secret place. Asynchronous keys have one very positive property: the public key, with which the digital signature is verified, can be transmitted over open communication channels, and the signature itself is performed using a private key that cannot be calculated (within a reasonable time) with a public key in hand. A few messages ago, Masha gave Vitya a new public key to verify messages, and now, even if this message is decrypted, all that can be done with this key is to check the authenticity of the message.

Masha signs a new message in which she speaks of failure and signs it with a private key, now she is sure that Victor will trust her message and the attackers will not be able to compromise their communication channel.

func SignData(data []byte, privateKey string) ([]byte, error) {
  private, err := getPrivateKey(privateKey)
  if err != nil {
     return nil, fmt.Errorf("cannot parse private key: %w", err)
  }
  sign, err := rsa.SignPSS(rand.Reader, private, signHashFn, hashData(data), nil)
  if err != nil {
     return nil, fmt.Errorf("error while signing: %w", err)
  }
  return sign, nil
}

func SignVerify(data, sign []byte, publicKey string) error {
  public, err := getPublicKey(publicKey)
  if err != nil {
     return fmt.Errorf("cannot parse public key `%s`: %w", publicKey, err)
  }
  err = rsa.VerifyPSS(public, signHashFn, hashData(data), sign, nil)
  if err != nil {
     return fmt.Errorf("error while sign checking: %w", err)
  }
  return nil
}

Conclusion

In conclusion, I want to thank the reader for helping Masha and Vita to establish a secret communication channel in public networks. But as you can imagine, it’s just a small game. In reality, everything is much more complicated and I have left out a lot of things here. For example, if Masha hides secret data in a PNG picture, then this is fawn. Well, you must admit, if you post photos on the network, then it’s probably a JPEG?
However, such an application is clearly enough to play secret agents with your friend (or girlfriend) and just get a feel for how you can protect communication channels in public networks.

As I said above, you can read the code on my github. In catalog crypt you will find all three described algorithms and two more hash functions – one for strengthening the XOR key, and the other for generating a fingerprint for a digital signature.

In folder demo find my PNG photo with a message encrypted inside, the keys necessary for decryption are stitched into decode.sh file that will allow you to receive the decrypted message and check its digital signature.
In folder carrier lies the code that allows you to break the message into bits and embed them in a PNG image. And to break the data into small pieces of bits that are easily embedded in the RGB vector, we are allowed by the code that lies in the folder nibbles. So everything here is very interesting.

And for those who do not have a GO compiler or who are too lazy, you can try my online steganography service, which I also mentioned in the first part of this article. Well, Masha and Vitya and I say goodbye to you, I hope not for long.