Can You Reverse f(f(f(x))+1)? Meet VMPC

Can You Reverse f(f(f(x))+1)? Meet VMPC

A big tip for anyone doing research … don’t dismiss a method just because it isn’t currently being used — as you may find new uses for it. At least, by reading the paper, you may find an interesting viewpoint. In these days of paper mills for research papers, it is often easy to forget how much effort can go into a paper, and which might involve years of work and refinement. One such paper was written by Bartosz Zoltak [LinkedIn] on VMPC (Variably Modified Permutation Composition) [1]:

While nearly 20 years old, it is still a valid paper in reviewing the usage of stream ciphers. Bartosz’s focus was to find a one-way function that was P=NP complete. With this, we could find a provable way that you can convert from A to B, but not B to A. This would give us a perfect hash function.

The VMPC one-way function is one of the simpliest one-way functions as it defined as:

F(F(F(x))+1)

Let try:

f(f(f(x))+1) (mod n)

If f(x) = x² with x=5 and n=997, we get:

f(f(5²)+1) (mod 997) = f(625+1) (mod 997) =55

It should then be difficult to go from 55 back to our original value of 5 (obviously our simple example is not secure as we have used small values).

With this basic method, Bartosz created the VMPC stream cipher (which will be outlined later in the article), and a random number generator (VMPC-R) [2]. He has since worked on the problem and produced 1,700 pages of notes [3]:

First we create a folder named “bc_vmpc”, and then go into that folder. We can create a Dotnet console project for .NET 8.0 with:

dotnet new console --framework net8.0

This produces a Csproject file of:

<Project Sdk="Microsoft.NET.Sdk">
<PropertyGroup>
        <OutputType>Exe</OutputType>
        <TargetFramework>net8.0</TargetFramework>
        <ImplicitUsings>enable</ImplicitUsings>
        <Nullable>enable</Nullable>
        </PropertyGroup>
 </Project>

We then add the latest Bouncy Castle library:

dotnet add package BouncyCastle.Cryptography --version 2.2.1

The following is the coding:

namespace VMPC
{
using Org.BouncyCastle.Crypto;
    using Org.BouncyCastle.Crypto.Engines;
    using Org.BouncyCastle.Crypto.Parameters;
    using Org.BouncyCastle.Security;
    class Program
    {
        
        static void Main(string[] args)
        {
            
            
          
         var msg="Hello";
  
          var iv="00112233445566778899AABBCCDDEEFF";
            var size=512;
          if (args.Length >0) msg=args[0];
          if (args.Length >1) iv=args[1];
        if (args.Length >2) size=Convert.ToInt32(args[2]);
          
  
             
            try {

var plainTextData=System.Text.Encoding.UTF8.GetBytes(msg);
var cipher = new VmpcEngine();

byte[] nonce = new byte[16]; 
Array.Copy(Convert.FromHexString(iv), nonce, 16);

CipherKeyGenerator keyGen = new CipherKeyGenerator();
keyGen.Init(new KeyGenerationParameters(new SecureRandom(), size));
KeyParameter keyParam = keyGen.GenerateKeyParameter();
ParametersWithIV keyParamIV = new ParametersWithIV(keyParam,nonce);

cipher.Init(true,keyParamIV);
int outputSize = plainTextData.Length;
byte[] cipherTextData = new byte[outputSize];
cipher.ProcessBytes(plainTextData, 0, plainTextData.Length, cipherTextData, 0);
var rtn =  cipherTextData;

// Decrypt
cipher.Init(false,keyParamIV);
outputSize = cipherTextData.Length;
plainTextData = new byte[outputSize];
cipher.ProcessBytes(cipherTextData, 0, cipherTextData.Length,plainTextData, 0);
var pln=plainTextData;

Console.WriteLine("=== {0} ==",cipher.AlgorithmName);
Console.WriteLine("Message:\t\t{0}",msg);
Console.WriteLine("IV:\t\t\t{0}",iv); 
Console.WriteLine("Key size:\t\t{0} bits",size);
Console.WriteLine("Key:\t\t\t{0} [{1}]",Convert.ToHexString(keyParam.GetKey()),Convert.ToBase64String(keyParam.GetKey()));

Console.WriteLine("\nCipher (hex):\t\t{0}",Convert.ToHexString(rtn));
Console.WriteLine("Cipher (Base64):\t{0}",Convert.ToBase64String(rtn));
Console.WriteLine("\nPlain:\t\t\t{0}",System.Text.Encoding.ASCII.GetString(pln).TrimEnd('\0'));

    } catch (Exception e) {
    Console.WriteLine("Error: {0}",e.Message);
    }
    }
    }

}

A sample run is:

=== VMPC ==
Message:		Hello 123
IV:			00112233445566778899AABBCCDDEEFF
Key size:		512 bits
Key:			A942A9440AF0DA87653853279C6E4E81AD982C6A9003E2A7FEAAB4A23DBCAFE04795338353B991B030EA0416A41C5E274C3A44F8F7BDE8423406B75CE61982F7 [qUKpRArw2odlOFMnnG5Oga2YLGqQA+Kn/qq0oj28r+BHlTODU7mRsDDqBBakHF4nTDpE+Pe96EI0Brdc5hmC9w==]
Cipher (hex):  7A2DE217CB3EAA8429
Cipher (Base64): ei3iF8s+qoQp
Plain:   Hello 123

Conclusions

In some places, research has become a bit of a game, and where there is no real soul in publishing work. Often it is a turn-key approach to publishing, and where there is no real mission or vision. For Bartosz, it is a mission and a challenge that he must solve.

References

[1] Zoltak, B. (2004). VMPC one-way function and stream cipher. In Fast Software Encryption: 11th International Workshop, FSE 2004, Delhi, India, February 5–7, 2004. Revised Papers 11 (pp. 210–225). Springer Berlin Heidelberg.

[2] Zoltak, B. (2013). VMPC-R Cryptographically Secure Pseudo-Random Number Generator Alternative to RC4. Cryptology ePrint Archive.

[3] Zoltak, B. (2019). Message Authentication (MAC) Algorithm For The VMPC-R (RC4-like) Stream Cipher. Cryptology ePrint Archive.