How to incrementally iterate through all possible values of a byte array of size n?

Question

For my question n=16, but a generic answer would be appreciated too.

So I have a byte array:

byte[] key;

My problem is that I want to iterate through all possible values of each element in this array, combined. I know this will take ages, and I'm not looking to actually complete this loop, just to make a loop which will at least attempt this.

So e.g.:

First iteration:

//Math.Pow(2,128) is the max no. of iterations right?
byte[] key;
for(int i = 0; i < Math.Pow(2,128); i++)
{
   key = new byte[16] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
}

Second iteration:

//Math.Pow(2,128) is the max no. of iterations right?
byte[] key;
for(int i = 0; i < Math.Pow(2,128); i++)
{
   key = new byte[16] {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
}

Third iteration:

//Math.Pow(2,128) is the max no. of iterations right?
byte[] key;
for(int i = 0; i < Math.Pow(2,128); i++)
{
   key = new byte[16] {2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
}

Final iteration:

//Math.Pow(2,128) is the max no. of iterations right?
byte[] key;
for(int i = 0; i < Math.Pow(2,128); i++)
{
   key = new byte[16] {255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255};
}

Obviously I have just hardcoded the array above. I need a way of doing this in a proper way. Again, I know there are many different combinations. All I need is a way to start iterating through all possible values. How can I do this in my loop?

I.e. what should I replace the body of my loop with, in order to iterate through all possible values of a byte array of size 16.

What I have tried:

In the body of the loop I have tried the following:

key = new byte[16] { (byte)i, (byte)i, (byte)i, (byte)i, (byte)i, (byte)i, (byte)i, (byte)i, (byte)i, (byte)i, (byte)i, (byte)i, (byte)i, (byte)i, (byte)i, (byte)i };

Obviously wrong, will only test a small subset of possible values. Will just try i= 0,...,255 and then start over for when i=256 --> (byte)i = 0.

I suspect I need some more nesting. Possibly up to 16 nested loops, which sounds insane and probably wrong? I can't get my head around this problem, any help would be much appreciated!

Purpose: The purpose of this question is to demonstrate how inefficient brute force cryptanalysis is in practice. The rest of my program works, I'm just stuck in this loop.

Answer 1

In case you don't realize: 16 bytes is the size of a Guid or the size of a standard cryptographic key size. There are so many combinations that you cannot enumerate even a fraction. Maybe you can enumerate the last 8 bytes if you parallelize across 1000 machines and wait a year.

You could do that easily by running a for loop from 0 to ulong.MaxValue. I'm submitting this as an answer because this very simple idea allows you to start enumerating and essentially never come to a point where you finish.

for (ulong i = 0; i < ulong.MaxValue; i++) {
 var bytes = new [] {
   0, 0, 0, 0, 0, 0, 0, 0
   , (byte)(i >> (7 * 8))
   , (byte)(i >> (6 * 8))
   , (byte)(i >> (5 * 8))
   //...
   , (byte)(i >> (0 * 8)) };
}

Or, just use 16 nested for loops. I don't think that's insane at all because it is so simple that it's clearly correct.

Answer 2

this is a sample code without any exception handling and kind of inefficient to simulate a counter like the one you mentioned

public static void NextIteration(byte[] input)
{
    if (input.All(x => x == 255))
        throw new InvalidOperationException("there is no iteration left");

    var converted = input.Select(x => (int) x).ToArray();
    converted[0]++;
    for (var i = 0; i < converted.Length; i++)
    {
        if (converted[i] == 256)
        {
            converted[i] = 0;
            converted[i + 1]++;
        }
    }
    for (var i = 0; i < input.Length; i++)
    {
        input[i] = (byte) converted[i];
    }
}