続・Get-Randomで使われている乱数生成アルゴリズムについて調べてみた

PowerShell Advent Calendar 2017、13日目です。

qiita.com

以前に書いた、

blog.shibata.tech

の続きになります。

本エントリではPowerShell 6.0でGet-Randomで使われている乱数生成アルゴリズムがどう変化したか調べた結果について説明します。

はじめに

これまでのバージョンのPowerShellとPowerShell 6.0で大きく異なる点は、

• PowerShell Coreとして.NET Core製になったこと
• クロスプラットフォーム化

になります。

PowerShellはオープンソースになったので実際のソースを確認しながら上記の点を中心に変化を調べていきます。

PowerShell 6.0におけるGet-Randomの実装

現時点で最新のPowerShell 6.0-RC(.NET Core 2.0.0)におけるGet-Randomの実装は、これまで通りGetRandomCommandクラスにあります。

ソースの基本的な構成はPowerShell 5.0～5.1の構成と大きく変わっておらず、乱数生成にはPolymorphicRandomNumberGeneratorクラスが使われています。

このクラスでは、-SetSeedパラメーターを指定してシードを指定した場合はSystem.Randomクラスを、シードを指定しない場合はSystem.Security.Cryptography.RandomNumberGeneratorクラスのRandomNumberGenerator.Create()メソッドから生成されるインスタンスを使って乱数生成を行います。

ここまでは前回と同様なのですが、それぞれのクラスは.NET Core版なので.NET Framework版のそれとは実装が異なります。

System.Randomクラスの実装について

System.Randomクラスの実装は.NET Coreでも変わっておらず、乱数生成にはKnuthの減算法に基づいたアルゴリズムが使用されます。
こちらについては変化はなく全てのプラットフォームにおいて共通です。

The Art of Computer Programming (2) 日本語版 Seminumerical algorithms Ascii Addison Wesley programming series

System.Security.Cryptography.RandomNumberGeneratorクラスの実装について

System.Security.Cryptography.RandomNumberGenerator.Create()メソッドの実装は.NET Coreでは大きく変わっています。

前回の場合ではこのメソッドによりSystem.Security.Cryptography.RNGCryptoServiceProvideクラスのインスタンスが生成されていましたが、.NET CoreではSystem.Security.Cryptography.RandomNumberGeneratorImplementationクラスのインスタンスが生成され、このRandomNumberGeneratorImplementationの実装はプラットフォーム毎に異なります。

WindowsにおけるRandomNumberGeneratorImplementationクラスの実装

RandomNumberGeneratorImplementationクラスのWindowsに固有の実装はこちらにあり、以下の様になっています。

using System.Diagnostics;

namespace System.Security.Cryptography
{
    partial class RandomNumberGeneratorImplementation
    {
        private unsafe void GetBytes(byte* pbBuffer, int count)
        {
            Debug.Assert(pbBuffer != null);
            Debug.Assert(count > 0);

            Interop.BCrypt.NTSTATUS status = Interop.BCrypt.BCryptGenRandom(pbBuffer, count);
            if (status != Interop.BCrypt.NTSTATUS.STATUS_SUCCESS)
                throw Interop.BCrypt.CreateCryptographicException(status);
        }
    }
}

乱数生成には

Interop.BCrypt.BCryptGenRandom(pbBuffer, count);

とSystem.Interop.BCryptクラスが使われ以下の様に定義されています。

using System;
using System.Diagnostics;
using System.Runtime.InteropServices;

internal partial class Interop
{
    internal partial class BCrypt
    {
        internal static unsafe NTSTATUS BCryptGenRandom(byte* pbBuffer, int count)
        {
            Debug.Assert(pbBuffer != null);
            Debug.Assert(count >= 0);

            return BCryptGenRandom(IntPtr.Zero, pbBuffer, count, BCRYPT_USE_SYSTEM_PREFERRED_RNG);
        }

        private const int BCRYPT_USE_SYSTEM_PREFERRED_RNG = 0x00000002;

        [DllImport(Libraries.BCrypt, CharSet = CharSet.Unicode)]
        private static extern unsafe NTSTATUS BCryptGenRandom(IntPtr hAlgorithm, byte* pbBuffer, int cbBuffer, int dwFlags);
    }
}

最終的に乱数生成にはCryptography API: Next Generation(CNG)のBCryptGenRandom関数が使われます。

この関数で使われるアルゴリズムについてですが...よくわかりませんでした。
セキュリティに詳しい方がいらっしゃいましたら是非教えてください。

【ちょっと追記】

BCryptGenRandom関数の定義に、

The default random number provider implements an algorithm for generating random numbers that complies with the NIST SP800-90 standard, specifically the CTR_DRBG portion of that standard.

とあるので、デフォルトではNIST SP 800-90というアルゴリズムが使われるようです。

.NET Coreの実装はおそらくデフォルト指定なのでPowerShellにおいもこのアルゴリズムが使われていそうです。
ただ、このアルゴリズムがどんなものなのかはさっぱりです...

Unix(Linux)におけるRandomNumberGeneratorImplementationクラスの実装

RandomNumberGeneratorImplementationクラスのUnixに固有の実装はこちらにあり、以下の様になっています。

using System.Diagnostics;

namespace System.Security.Cryptography
{
    partial class RandomNumberGeneratorImplementation
    {
        private unsafe void GetBytes(byte* pbBuffer, int count)
        {
            Debug.Assert(pbBuffer != null);
            Debug.Assert(count > 0);

            if (!Interop.Crypto.GetRandomBytes(pbBuffer, count))
            {
                throw Interop.Crypto.CreateOpenSslCryptographicException();
            }
        }
    }
}

乱数生成には

Interop.Crypto.GetRandomBytes(pbBuffer, count);

とUnix固有のSystem.Interop.Cryptクラスが使われています。
このクラスの実装に関して、使用されるアルゴリズム毎に実装されるファイルが分かれているのですが、GetRandomBytesに関しては"おそらく"Interop.RAND.csファイルの実装が使われる様です。*1

この実装については以下の様になっています。

using System.Diagnostics;
using System.Runtime.InteropServices;

internal static partial class Interop
{
    internal static partial class Crypto
    {
        internal static unsafe bool GetRandomBytes(byte* pbBuffer, int count)
        {
            Debug.Assert(pbBuffer != null);
            Debug.Assert(count >= 0);

            return CryptoNative_GetRandomBytes(pbBuffer, count);
        }

        [DllImport(Libraries.CryptoNative)]
        [return: MarshalAs(UnmanagedType.Bool)]
        private static extern unsafe bool CryptoNative_GetRandomBytes(byte* buf, int num);
    }
}

内部で呼ばれているCryptoNative_GetRandomBytesの実装はこちらにあり、抜粋すると以下の実装となっています。

/*
Function:
GetRandomBytes
Puts num cryptographically strong pseudo-random bytes into buf.
Return values:
Returns a bool to managed code.
1 for success
0 for failure
*/
extern "C" int32_t CryptoNative_GetRandomBytes(uint8_t* buf, int32_t num)
{
    int ret = RAND_bytes(buf, num);

    return ret == 1;
}

最終的にはOpenSSLのRAND_bytes関数が使われています。

アルゴリズムについては...こちらもよくわかりませんでした...orz

【ちょっと追記】

細かい話がWikiに載っているようなので、気になる方は調べてみるとよいかもしれません。

macOSにおけるRandomNumberGeneratorImplementationクラスの実装

最後に、RandomNumberGeneratorImplementationクラスのmacOSに固有の実装はこちらにあり、以下の様になっています。

using System.Diagnostics;

namespace System.Security.Cryptography
{
    partial class RandomNumberGeneratorImplementation
    {
        private unsafe void GetBytes(byte* pbBuffer, int count)
        {
            Debug.Assert(pbBuffer != null);
            Debug.Assert(count > 0);

            Interop.AppleCrypto.GetRandomBytes(pbBuffer, count);
        }
    }
}

乱数生成には

Interop.AppleCrypto.GetRandomBytes(pbBuffer, count);

とSystem.Interop.AppleCryptoクラスが使われ以下の様に定義されています。

using System.Diagnostics;
using System.Runtime.InteropServices;
using System.Security.Cryptography;

internal static partial class Interop
{
    internal static partial class AppleCrypto
    {
        internal static unsafe void GetRandomBytes(byte* pbBuffer, int count)
        {
            Debug.Assert(pbBuffer != null);
            Debug.Assert(count >= 0);

            int errorCode;
            int ret = AppleCryptoNative_GetRandomBytes(pbBuffer, count, out errorCode);

            if (ret == 0)
            {
                throw CreateExceptionForCCError(errorCode, CCRNGStatus);
            }

            if (ret != 1)
            {
                throw new CryptographicException();
            }
        }

        [DllImport(Libraries.AppleCryptoNative)]
        private static extern unsafe int AppleCryptoNative_GetRandomBytes(byte* buf, int num, out int errorCode);
    }
}

内部で呼ばれているAppleCryptoNative_GetRandomBytesの実装はこちらにあり、以下の実装となっています。

#include "pal_random.h"

#include <CommonCrypto/CommonCrypto.h>
#include <CommonCrypto/CommonRandom.h>

extern "C" int32_t AppleCryptoNative_GetRandomBytes(uint8_t* pBuf, uint32_t cbBuf, int32_t* pkCCStatus)
{
    if (pBuf == nullptr || pkCCStatus == nullptr)
        return -1;

    CCRNGStatus status = CCRandomGenerateBytes(pBuf, cbBuf);
    *pkCCStatus = status;
    return status == kCCSuccess;
}

最終的に乱数生成にはCommonCryptoのCCRandomGenerateBytes関数が使われています。

アルゴリズムは、というかこのライブラリ自体がどういったものかよくわかりません。
OS標準の機能なんですよね？多分...
Macに詳しい方なら余裕でわかるものなのでしょうか？

まとめ

アルゴリズムの詳細についてはわからないことだらけでしたが、実装については明らかにできたかと思います。

前回の分と合わせてGet-Randomの実装をまとめると、

• PowerShell 2.0 ～ 4.0

  • シード指定あり => .NET FrameworkのSystem.Randomクラスで乱数生成
  • シード指定なし => .NET FrameworkのSystem.Randomクラスで乱数生成

• PowerShell 5.0 ～ 5.1

  • シード指定あり => .NET FrameworkのSystem.Randomクラスで乱数生成
  • シード指定なし => .NET FrameworkのSystem.Security.Cryptography.RNGCryptoServiceProviderクラスで乱数生成

• PowerShell 6.0

  • シード指定あり => .NET CoreのSystem.Randomクラスで乱数生成
    • Randomクラスの実装は全プラットフォーム共通
  • シード指定なし => .NET CoreのSystem.Security.Cryptography.RandomNumberGeneratorImplementationクラスで乱数生成
    • RandomNumberGeneratorImplementationクラスの実装はプラットフォーム毎に異なる

となります。

*1:正直ちょっと自信がありません...