5
\$\begingroup\$

I have the following code that I wrote in order to find the correct password by generating hashes out of all possible combinations and comparing each of them with the target. I'm trying to make GetPasswordFromHash() as efficient as possible, in regards to multi-threading, and I've decided to pick PLINQ for that.

Scrypt/Pbkdf2 functions come from CryptSharpStandard library and they're CPU-bound tasks that generate password hashes (returning byte[]). I've verified that this implementation works correctly for my use case (I'll be given only password hash and salt to work with), but if you have any other library recommendations, I'm also willing to check them out.

Right now, the correct result is generated in approx 1m30s on my machine, while single-threaded solution took at least 3x as much (approx 300s, both tested on my i7 7700k box).

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using CryptSharp.Utility;

namespace CryptTest {
    internal static class Program {
        // Those 3 are provided by third-party, they're not expected to be configurable
        private const byte BlocksCount = 8;
        private const ushort Pbkdf2IterationsCount = 10000;
        private const ushort ScryptIterationsCount = 8192;

        private static IEnumerable<byte[]> AllPasswordCodes {
            get {
                for (char a = '0'; a <= '9'; a++) {
                    for (char b = '0'; b <= '9'; b++) {
                        for (char c = '0'; c <= '9'; c++) {
                            for (char d = '0'; d <= '9'; d++) {
                                yield return new[] { (byte) a, (byte) b, (byte) c, (byte) d };
                            }
                        }
                    }
                }
            }
        }

        internal static string GetPasswordFromHash(byte[] passwordHash, byte[] salt, bool scrypt = true) {
            if ((passwordHash == null) || (salt == null)) {
                return null;
            }

            byte[] password = scrypt
                ? AllPasswordCodes.AsParallel().FirstOrDefault(passwordToTry => passwordHash.SequenceEqual(SCrypt.ComputeDerivedKey(passwordToTry, salt, ScryptIterationsCount, BlocksCount, 1, null, passwordHash.Length)))
                : AllPasswordCodes.AsParallel().FirstOrDefault(
                    passwordToTry => {
                        using (HMACSHA1 hmacAlgorithm = new HMACSHA1(passwordToTry)) {
                            return passwordHash.SequenceEqual(Pbkdf2.ComputeDerivedKey(hmacAlgorithm, salt, Pbkdf2IterationsCount, passwordHash.Length));
                        }
                    }
                );

            return password != null ? Encoding.UTF8.GetString(password) : null;
        }

        private static void Main() {
            // Main() is used for benchmarking and verification only, no need to focus on that besides correctness
            byte[] salt = new byte[7];

            using (RNGCryptoServiceProvider crypto = new RNGCryptoServiceProvider()) {
                crypto.GetNonZeroBytes(salt);
            }

            byte[] password = { (byte) '1', (byte) '3', (byte) '3', (byte) '7' };
            byte[] passwordHash = SCrypt.ComputeDerivedKey(password, salt, ScryptIterationsCount, BlocksCount, 1, null, 32);

            Stopwatch watch = new Stopwatch();

            watch.Start();

            string generatedPassword = GetPasswordFromHash(passwordHash, salt);

            watch.Stop();

            Console.WriteLine("Verification: " + Encoding.UTF8.GetBytes(generatedPassword).SequenceEqual(password));
            Console.WriteLine("Time elaped: " + watch.Elapsed);
            Console.ReadLine();
        }
    }
}

I'm trying to balance the code readability/size with the performance benefits, and I'm quite happy with the current solution, although at the same time I'm wondering if there is anything else to improve in regards to that. I can (and will) make appropriate benchmarks myself, this is more about code analysis and ideas for improvements, rather than checking whether solution X will do better/worse than current one, I can check that myself. Please feel free to share your suggested code edits or ideas, I'll greatly appreciate and check all of them. Even if you can't think of anything better, I also value your response as it gives me feedback in terms of correct solution.

Thank you in advance for your time!

\$\endgroup\$
  • \$\begingroup\$ Is there a use case for brute forcing hashes against this input? I just wonder why you want to implement such a function. \$\endgroup\$ – dfhwze Jul 20 at 14:23
  • \$\begingroup\$ @dfhwze Yes, I'm using it as a recovery mechanism for lost passwords in a particular third-party service which provides me with hash and salt. No, I don't maintain that third-party service, I'm only providing the missing functionality based on a possibility. The service provides those credentials for the client to verify his password against the saved one. I could provide the exact service details but I don't think they're needed or appropriate. It's not used with any malicious intent, since the service provides those details intentionally upon request (which requires prior authorization). \$\endgroup\$ – JustArchi Jul 20 at 14:51
  • \$\begingroup\$ Interesting feature of that API. Seems like paradise for h3ckor². \$\endgroup\$ – dfhwze Jul 20 at 14:56
  • \$\begingroup\$ Yes, I fully realize the loophole they've created, and I also have the same opinion as you. The only supportive argument is the fact that this is extra authorization (parental control) upon already authenticated account, which could be "justified" as "it's just a stupid code to stop children from accessing several service features", but it still could be done better, in at least several different ways. Well, I'm luckily not in charge of that API or service, just making a helper function for those in need (or script kiddies I guess...). In any case, thanks for your concern, I appreciate it. \$\endgroup\$ – JustArchi Jul 20 at 15:02
  • \$\begingroup\$ I tried compiling using CryptSharp v1.3.0 (latest stable), but the method signatures don't match. \$\endgroup\$ – dfhwze Jul 20 at 15:28
6
\$\begingroup\$

I'm trying to balance the code readability/size with the performance benefits, ..

Your code could be optimized for readability and object-oriented design without introducing a performance penalty.


The entropy generation could be written more elegantly.

original code

for (char a = '0'; a <= '9'; a++) {
    for (char b = '0'; b <= '9'; b++) {
        for (char c = '0'; c <= '9'; c++) {
            for (char d = '0'; d <= '9'; d++) {
                yield return new[] { (byte) a, (byte) b, (byte) c, (byte) d };
            }
        }
    }
}

refactored

static class EntropyGenerator
{
    public static IEnumerable<byte> ValidChars => Enumerable.Range('0', 10).Select(c => (byte)c).ToList();

    public static IEnumerable<byte[]> GenerateEntropy()
    {
        return (from a in ValidChars
                from b in ValidChars
                from c in ValidChars
                from d in ValidChars
                select new[] { a, b, c, d });
    }
}

GetPasswordFromHash has repeating code and an ugly switch that could be refactored into a strategy pattern.

First, we should create an enum and interface for the strategies. It would have helped if this API came with its own interface.

interface IHashProvider
{
    byte[] ComputeDerivedKey(byte[] key, byte[] salt, int derivedKeyLength);
}

enum HashProviderAlgorithm
{
    SCrypt,
    Pbkdf2
}

We can then implement both strategies.

class ScryptHashProvider : IHashProvider
{
    private const byte BlocksCount = 8;
    private const ushort IterationsCount = 8192;

    public byte[] ComputeDerivedKey(byte[] key, byte[] salt, int derivedKeyLength)
    {
        return SCrypt.ComputeDerivedKey(key, salt, IterationsCount, BlocksCount, 1, null, derivedKeyLength);
    }
}

class Pbkdf2HashProvider : IHashProvider
{
    private const ushort IterationsCount = 10000;

    public byte[] ComputeDerivedKey(byte[] key, byte[] salt, int derivedKeyLength)
    {
        using (var hmac = new HMACSHA1(key))
        {
            return Pbkdf2.ComputeDerivedKey(hmac, salt, IterationsCount, derivedKeyLength);
        }
    }
}

So the password recovery mechanism can be written much more elegantly.

class PasswordRecovery
{
    IEnumerable<byte[]> Entropy { get; }
    IDictionary<HashProviderAlgorithm, IHashProvider> Providers { get; }

    public PasswordRecovery(IEnumerable<byte[]> entropy)
    {
        Entropy = entropy ?? throw new ArgumentNullException(nameof(entropy));
        Providers = new Dictionary<HashProviderAlgorithm, IHashProvider>
        {
            { HashProviderAlgorithm.SCrypt, new ScryptHashProvider() },
            { HashProviderAlgorithm.Pbkdf2, new Pbkdf2HashProvider() }
        };
    }

    public string RecoverPassword(byte[] passwordHash, byte[] salt, HashProviderAlgorithm algorithm = default)
    {
        if (passwordHash == null)
            throw new ArgumentNullException(nameof(passwordHash));
        if (salt == null)
            throw new ArgumentNullException(nameof(salt));

        var entropy = Entropy.AsParallel();
        var provider = Providers[algorithm];
        var password = entropy.FirstOrDefault(
            pwd => passwordHash.SequenceEqual(provider.ComputeDerivedKey(pwd, salt, passwordHash.Length)));

        if (password == null)
            throw new ArgumentException("Unable to recover password given the specified entropy, hash and salt");

        return Encoding.UTF8.GetString(password);
    }
}

And our verification test:

// arrange
var salt = new byte[7];
using (var crypto = new RNGCryptoServiceProvider())
{
    crypto.GetNonZeroBytes(salt);
}
var password = new [] { (byte)'1', (byte)'3', (byte)'3', (byte)'7' };
var passwordHash = SCrypt.ComputeDerivedKey(password, salt, 8192, 8, 1, null, 32);

// act
var entropy = EntropyGenerator.GenerateEntropy();
var passwordRecovery = new PasswordRecovery(entropy);
var generatedPassword = passwordRecovery.RecoverPassword(passwordHash, salt);

// assert
var recovered = Encoding.UTF8.GetBytes(generatedPassword).SequenceEqual(password);
Assert.IsTrue(recovered);
\$\endgroup\$
  • \$\begingroup\$ Thanks a lot! I'll for sure make use of it. \$\endgroup\$ – JustArchi Jul 20 at 16:33
  • 1
    \$\begingroup\$ oh, and when the password is not found I would throw an exception like PasswordNotFoundException, ArgumentException is for arguments which in this case are technically correct but just the wrong guess. \$\endgroup\$ – t3chb0t Jul 20 at 16:34
  • 1
    \$\begingroup\$ @t3chb0t I hate creating a new exception class for this :) I don't have DynamicException, so perhaps KeyNotFoundException or something. \$\endgroup\$ – dfhwze Jul 20 at 16:45
  • 2
    \$\begingroup\$ +1; though I don't like the HashProviderAlgorithm algorithm = default: this doesn't really document the intention. I'd rather it was explicitly HashProviderAlgorithm algorithm = HashProviderAlgorithm.Scrypt, and that the enum options were assigned explicit values if they are going to be used as default values; otherwise, I'd probably make it non-optional and provide an overload, so that HashProviderAlgorithm.Scrypt isn't baked at compile-time. All that said, I'd probably drop the enum altogether and just pass in the interface. \$\endgroup\$ – VisualMelon Jul 20 at 17:35
  • 1
    \$\begingroup\$ @VisualMelon Good points. I took over the default because the OP did the same thing (but I shouldn't have). My solution is an archaic SPI style, where an algorithm is specified by name (or enum), not by interface. Dropping the enum seems a more flexible and contemporary choice. \$\endgroup\$ – dfhwze Jul 20 at 17:38
4
\$\begingroup\$

dfhwze has addressed the structural and other issues with the code, so I will focus on eliminating the pyramid of doom in AllPasswordCodes:

    private static IEnumerable<byte[]> AllPasswordCodes {
        get {
            for (char a = '0'; a <= '9'; a++) {
                for (char b = '0'; b <= '9'; b++) {
                    for (char c = '0'; c <= '9'; c++) {
                        for (char d = '0'; d <= '9'; d++) {
                            yield return new[] { (byte) a, (byte) b, (byte) c, (byte) d };
                        }
                    }
                }
            }
        }
    }

It can be done in a single loop in the following way:

public static IEnumerable<Byte[]> GetAllPasswords()
{
  for (int i = 0; i < 1e4; i++)
  {
    yield return Encoding.ASCII.GetBytes(i.ToString("0000"));
  }
}

It's maybe a few milliseconds slower, but IMO more maintainable.

Alternatively you can do:

public static IEnumerable<Byte[]> GetAllPasswords()
{
  for (int i = 0; i < 1e4; i++)
  {
    yield return new byte[] 
    {
      (byte)('0' + i / 1000),
      (byte)('0' + i % 1000 / 100),
      (byte)('0' + i % 100 / 10),
      (byte)('0' + i % 10)
    };
  }
}

Which seems to have same performance as the original.

As shown I've changed it from a property to a method, because IMO a property shouldn't execute code in this way to return. Alternatively you could make a class implementing IEnumerable<T>:

  class PasswordEnumerator : IEnumerable<byte[]>
  {
    public IEnumerator<byte[]> GetEnumerator()
    {
      for (int i = 0; i < 1e4; i++)
      {
        yield return new byte[] 
        {
          (byte)('0' + i / 1000),
          (byte)('0' + i % 1000 / 100),
          (byte)('0' + i % 100 / 10),
          (byte)('0' + i % 10)
        };
      }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
      return GetEnumerator();
    }
  }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.