Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

crypto/rand: Currently using deprecated API for random number generation on Windows #33542

Closed
randomvariable opened this issue Aug 8, 2019 · 22 comments

Comments

@randomvariable
Copy link

@randomvariable randomvariable commented Aug 8, 2019

What version of Go are you using (go version)?

N/A

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

Any release of Windows supported by Microsoft

What did you do?

Reviewing cryptographic protocols for a downstream project

What did you expect to see?

Use of a modern Windows API to retrieve entropy, namely BCryptGenRandom from CryptoNG, which is compliant with CTR_DRBG from NIST SP800-90.

What did you see instead?

Go calls CryptGenRandom from a deprecated API. The algorithm is not fully documented and is only known in part.

@bcmills bcmills added this to the Go1.14 milestone Aug 8, 2019
@bcmills
Copy link
Member

@bcmills bcmills commented Aug 8, 2019

@jtn7
Copy link

@jtn7 jtn7 commented Dec 5, 2019

I noticed, recently, that crypto/rand used CryptGenRandom instead of (BCryptGenRandom). So I decided to call it manually.

In case anyone is interested:

var (
	bcrypt, libErr     = syscall.LoadLibrary("bcrypt.dll")
	genRandom, procErr = syscall.GetProcAddress(bcrypt, "BCryptGenRandom")
)

const BCRYPT_USE_SYSTEM_PREFERRED_RNG = 0x00000002

func bcryptGenRandom(buf []byte) (ret uintptr, callErr error) {
	const nargs = 4
	ret, _, callErr = syscall.Syscall6(
		genRandom,
		nargs,
		0,
		uintptr(unsafe.Pointer(&buf[0])),
		uintptr(len(buf)),
		BCRYPT_USE_SYSTEM_PREFERRED_RNG,
		0,
		0,
	)
	return
}
@zx2c4
Copy link
Contributor

@zx2c4 zx2c4 commented Dec 5, 2019

The RNG function that we should be using on Windows is actually RtlGenRandom. I'll submit a patch to use that. We already have a wrapper around it in getRandomData.

@gopherbot
Copy link

@gopherbot gopherbot commented Dec 5, 2019

Change https://golang.org/cl/210057 mentions this issue: crypto/rand: generate random numbers using RtlGenRandom on Windows

@FiloSottile FiloSottile modified the milestones: Unplanned, Go1.15 Dec 5, 2019
@randomvariable
Copy link
Author

@randomvariable randomvariable commented Dec 6, 2019

Most confusing documentation ever, Microsoft...

@zikaeroh
Copy link
Contributor

@zikaeroh zikaeroh commented Dec 6, 2019

Out of curiosity (forgive my minimal experience in this area), why RtlGenRandom?

I was curious and looked at the docs for these APIs, and it seems like the docs for RtlGenRandom say "use CryptGenRandom" (the thing that this issue is saying is deprecated), and the docs for CryptGenRandom say "use CNG", i.e. BCryptGenRandom.

@jtn7
Copy link

@jtn7 jtn7 commented Dec 7, 2019

@zikaeroh According to this rust issue CryptGenRandom eventually makes call to RtlGenRandom. Another comment, in that issue, makes a more compelling argument: rust-random/rand#111 (comment). The comment explains that Microsoft uses it in their C standard library function rand_s and RtlGenRandom isn't going anywhere.

Looking at rust source I see references to both RtlGenRandom and BCryptGenRandom.

@zx2c4
Copy link
Contributor

@zx2c4 zx2c4 commented Dec 10, 2019

Time to reverse engineer some stuff.

RtlGenRandom/SystemFunction036 in advapi32.dll is a stub for cryptbase.dll, which has it as:

bool SystemFunction036(void *buf, uint32_t len)
{
  return ProcessPrng(buf, len);
}

ProcessPrng lives in bcryptPrimitives.dll as:

bool ProcessPrng(void *buf, uint64_t len)
{
  bool ret = true;
  uint64_t bytes_to_read;
  int64_t out;
  uint128_t *aes_key;

  success_1 = 1;
  if (g_rngState == 1)
  {
    ret = false;
    out = 0;
    AesRNGState_select(&aes_key);
    for (; len; len -= bytes_to_read)
    {
      bytes_to_read = 0x10000;
      if (len < 0x10000)
        bytes_to_read = len;
      buf += bytes_to_read;
      ret = AesRNGState_generate(aes_key, buf, bytes_to_read, &out);
    }
  }
  else
  {
    if (g_rngState != 2)
    {
      for (;;)
        *(unsigned int *)0 = 0x78676E72;
    }
    EmergencyRng(buf, len);
  }
  return ret;
}

From there I assume that this is some sort of per-process and per-cpu expansion machine mostly in userspace, seeded with some kernel entropy.

@alexbrainman
Copy link
Member

@alexbrainman alexbrainman commented Dec 11, 2019

we should be using on Windows is actually RtlGenRandom

The RtlGenRandom doco

https://docs.microsoft.com/en-us/windows/win32/api/ntsecapi/nf-ntsecapi-rtlgenrandom

suggests that we should use CryptGenRandom

It may be altered or unavailable in subsequent versions. Instead, use the CryptGenRandom function

@zx2c4 why do you prefer RtlGenRandom to current CryptGenRandom? I am fine with either.

Also, if we follow CryptGenRandom doco

https://docs.microsoft.com/en-us/windows/win32/api/wincrypt/nf-wincrypt-cryptgenrandom

This API is deprecated. New and existing software should start using Cryptography Next Generation APIs.

We should, probably, use BCryptGenRandom. No?

Alex

@tmthrgd
Copy link
Contributor

@tmthrgd tmthrgd commented Dec 18, 2019

@FiloSottile FiloSottile modified the milestones: Go1.15, Backlog Mar 31, 2020
@neolit123
Copy link
Contributor

@neolit123 neolit123 commented May 5, 2020

with latest Golang not supporting Windows XP would it be fine to replace the backend stdlib is using to BCryptGenRandom?

err = syscall.CryptGenRandom(r.prov, uint32(len(b)), &b[0])

if yes, i can send the change for that.

BoringSSL uses RtlGenRandom

the DLL export of SystemFunction036 is not guaranteed in the future, so i don't think this function should be used.

@zx2c4
Copy link
Contributor

@zx2c4 zx2c4 commented May 5, 2020

the DLL export of SystemFunction036 is not guaranteed in the future, so i don't think this function should be used.

SystemFunction036 isn't going to be going away. Not a chance Microsoft would break decades of applications. That's now proper API.

@neolit123
Copy link
Contributor

@neolit123 neolit123 commented May 6, 2020

That's now proper API.

it's hard to trust this based on the documentation for the function. Windows APIs have definitely gone away in the past.

are there actual benefits of using RtlGenRandom over BCryptGenRandom?

@gopherbot
Copy link

@gopherbot gopherbot commented May 7, 2020

Change https://golang.org/cl/232860 mentions this issue: crypto/rand: use BCryptGenRandom instead of CryptGenRandom on Windows

@neolit123
Copy link
Contributor

@neolit123 neolit123 commented May 7, 2020

see https://go-review.googlesource.com/c/go/+/232860

hi, this is the opposite proposal to https://go-review.googlesource.com/c/go/+/210057
where a the undocumented function RtlGenRandom is used:
https://docs.microsoft.com/en-us/windows/win32/api/ntsecapi/nf-ntsecapi-rtlgenrandom

xref https://docs.microsoft.com/en-us/windows/win32/api/ntsecapi/nf-ntsecapi-rtlgenrandom

with that particular backend, we do not know:

  • what is the underlying implementation and standard
  • when and if the exported function SystemFunction036 will be removed.

this change on the other hand uses BCryptGenRandom which is the new recommended API by Microsoft and as the issue #33542 mentions is compliant with NIST SP800-90:

https://docs.microsoft.com/en-us/windows/win32/api/bcrypt/nf-bcrypt-bcryptgenrandom#remarks

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.

neolit123 added a commit to neolit123/go that referenced this issue May 8, 2020
The existing function that is used is CryptGenRandom. This function
and the whole underling API is deprecated.

Use the function BCryptGenRandom from the new recommended
API called "Cryptography API: Next Generation (CNG)".

Fixes golang#33542
neolit123 added a commit to neolit123/go that referenced this issue May 8, 2020
The existing function that is used is CryptGenRandom. This function
and the whole underling API is deprecated.

Use the function BCryptGenRandom from the new recommended
API called "Cryptography API: Next Generation (CNG)".

Fixes golang#33542
@alexbrainman
Copy link
Member

@alexbrainman alexbrainman commented May 9, 2020

We have 2 alternative CLs to replace CryptGenRandom

CL 210057 uses RtlGenRandom (aka advapi32.SystemFunction036)

CL 232860 uses BCryptGenRandom

Lets decide here which one to pick. I don't have preference. What about others?

Thank you.

Alex

@alexbrainman alexbrainman reopened this May 9, 2020
@zx2c4
Copy link
Contributor

@zx2c4 zx2c4 commented May 9, 2020

RtlGenRandom:

  • Is used by a great many microsoft system executables and language runtimes (msvcrt.dll for example).
  • Is used by boringssl.
  • Is something I've reversed and understand well. Appears to call directly into bcryptprimitivedll's ProcessPrng, which is then an aes expansion machine that feels pretty similar to the fortuna paper (whose authors wrote this code here).
  • Is fast, well tested, and been around for a long time.

BCryptGenRandom:

  • Has an abstraction layer in front of it and more moving pieces, making it slower and eventually winds up calling RtlGenRandom.
  • Isn't used by boringssl.

The boringssl authors did heavy research here and contacted the owners of the bcrypt code. They decided to stick with RtlGenRandom and only fall back to BCryptGenRandom when absolutely desperate, for the UWP case, which Go does not support anyway. I suggest we follow their lead, and stick with RtlGenRandom. When (if?) we eventually port to UWP, we can reinvestigate, and also see the status of boringssl, to see whether we should still prefer RtlGenRandom and only fallback if necessary, or switch to BCryptGenRandom entirely. But that time is not now, and so I'd suggest we stick with the tried and true RtlGenRandom instead getting too caught up in whatever microsoft's new crypto api of the year presently is.

@alexbrainman
Copy link
Member

@alexbrainman alexbrainman commented May 9, 2020

RtlGenRandom

Thank you, Jason. (You can be pretty good salesmen!)

Anyone wants to say few good words about BCryptGenRandom? Apart from this page

https://docs.microsoft.com/en-us/windows/win32/api/wincrypt/nf-wincrypt-cryptgenrandom

vaguely recommends it as a replacement for CryptGenRandom (which we use now).

Alex

@neolit123
Copy link
Contributor

@neolit123 neolit123 commented May 9, 2020

@alexbrainman hello, when is the deadline for one of the changes to merge with respect to the golang 1.15 release cycle?

on Monday, i can try asking someone from the Microsoft cryptography team to add an up-to-date comment here to facilitate your mediation.


@zx2c4 hello,

https://bugs.chromium.org/p/boringssl/issues/detail?id=307

i'm not convinced the ticket in question landed on a good rationale for the default usage for RtlGenRandom on non-UWP platforms for boringssl.

Has an abstraction layer in front of it and more moving pieces, making it slower and eventually winds up calling RtlGenRandom.

i did some benchmarks on a couple of systems with different versions of Windows and different CPUs and bellow i have posted the results. please let me know if you think my tests are flawed in any way.

results from a Windows 7 system with Intel-i3:

Veryfing timer precision; result should be close to 1.0, got 0.999352
TestIterations: 100000

BufferSize: 1
BCryptGenRandom: 0.097258s
RtlGenRandom: 0.100814s

BufferSize: 2
BCryptGenRandom: 0.095720s
RtlGenRandom: 0.100624s

BufferSize: 4
BCryptGenRandom: 0.095737s
RtlGenRandom: 0.100634s

BufferSize: 8
BCryptGenRandom: 0.095641s
RtlGenRandom: 0.100441s

BufferSize: 16
BCryptGenRandom: 0.095755s
RtlGenRandom: 0.100434s

BufferSize: 32
BCryptGenRandom: 0.108264s
RtlGenRandom: 0.113315s

BufferSize: 64
BCryptGenRandom: 0.133766s
RtlGenRandom: 0.139911s

BufferSize: 128
BCryptGenRandom: 0.183334s
RtlGenRandom: 0.190524s

BufferSize: 256
BCryptGenRandom: 0.284192s
RtlGenRandom: 0.292344s

BufferSize: 512
BCryptGenRandom: 0.482821s
RtlGenRandom: 0.495196s

BufferSize: 1024
BCryptGenRandom: 0.879791s
RtlGenRandom: 0.902300s

BufferSize: 2048
BCryptGenRandom: 1.673630s
RtlGenRandom: 1.714524s

BufferSize: 4096
BCryptGenRandom: 3.260548s
RtlGenRandom: 3.340992s

BufferSize: 8192
BCryptGenRandom: 6.437690s
RtlGenRandom: 6.626667s

BufferSize: 16384
BCryptGenRandom: 12.841288s
RtlGenRandom: 13.214990s

results from a Windows 10 system with Intel-i7:

Veryfing timer precision; result should be close to 1.0, got 1.000995
TestIterations: 100000

BufferSize: 1
BCryptGenRandom: 0.009504s
RtlGenRandom: 0.004798s

BufferSize: 2
BCryptGenRandom: 0.008508s
RtlGenRandom: 0.007368s

BufferSize: 4
BCryptGenRandom: 0.009577s
RtlGenRandom: 0.009356s

BufferSize: 8
BCryptGenRandom: 0.011891s
RtlGenRandom: 0.007380s

BufferSize: 16
BCryptGenRandom: 0.014995s
RtlGenRandom: 0.008246s

BufferSize: 32
BCryptGenRandom: 0.014337s
RtlGenRandom: 0.011183s

BufferSize: 64
BCryptGenRandom: 0.021195s
RtlGenRandom: 0.021968s

BufferSize: 128
BCryptGenRandom: 0.034954s
RtlGenRandom: 0.025203s

BufferSize: 256
BCryptGenRandom: 0.040321s
RtlGenRandom: 0.031148s

BufferSize: 512
BCryptGenRandom: 0.044044s
RtlGenRandom: 0.043687s

BufferSize: 1024
BCryptGenRandom: 0.061089s
RtlGenRandom: 0.056259s

BufferSize: 2048
BCryptGenRandom: 0.108295s
RtlGenRandom: 0.098474s

BufferSize: 4096
BCryptGenRandom: 0.177441s
RtlGenRandom: 0.169848s

BufferSize: 8192
BCryptGenRandom: 0.318551s
RtlGenRandom: 0.310196s

BufferSize: 16384
BCryptGenRandom: 0.638916s
RtlGenRandom: 0.592175s

TL;DR summary

The functions behave close in performance where the Windows 10 / i7 system gives better results for RtlGenRandom, while the Windows 7 / i3 system gives better results for BCryptGenRandom with BCRYPT_USE_SYSTEM_PREFERRED_RNG.

source code:

// performance comparison between RtlGenRandom and BCryptGenRandom
// with BCRYPT_USE_SYSTEM_PREFERRED_RNG.
//
// gcc -O3 -std=c99 -Wall test.c -lbcrypt && a
#include <windows.h>
#include <stdio.h>
#include <bcrypt.h>

BOOLEAN(APIENTRY *RtlGenRandom)
	(void *, ULONG);

DOUBLE GetTime()
{
	LARGE_INTEGER t, f;
	QueryPerformanceCounter(&t);
	QueryPerformanceFrequency(&f);
	return (DOUBLE) t.QuadPart / (DOUBLE) f.QuadPart;
}

int PrepareRtlGenRandom()
{
	LoadLibrary("advapi32.dll");
	HMODULE advapi = GetModuleHandle("advapi32.dll");

	if (!advapi) {
		puts("advapi32 load error");
		return 1;
	}

	RtlGenRandom = (BOOLEAN(APIENTRY*)(void *, ULONG)) GetProcAddress(advapi, "SystemFunction036");
	if (!RtlGenRandom) {
		puts("RtlGenRandom proc error");
		return 1;
	}

	return 0;
}

int RunSingleTest(PBYTE Buffer, DWORD BufferSize, DWORD TestIterations)
{
	DOUBLE StartTime;
	printf("\nBufferSize: %lu\n", BufferSize);

	// test BCryptGenRandom
	StartTime = GetTime();
	for (int i = 0; i < TestIterations; i++) {
		if (BCryptGenRandom(
			NULL,
			Buffer,
			BufferSize,
			BCRYPT_USE_SYSTEM_PREFERRED_RNG)) {
			puts("BCryptGenRandom failed");
			return 1;
		}
	}

	printf("BCryptGenRandom: %fs\n", GetTime() - StartTime);

	// -------------------------------------------------------------------------

	// test RtlGenRandom
	StartTime = GetTime();
	for (int i = 0; i < TestIterations; i++) {
		if (!RtlGenRandom(Buffer, BufferSize)) {
			puts("RtlGenRandom failed");
			return 1;
		}
	}

	printf("RtlGenRandom: %fs\n", GetTime() - StartTime);
	return 0;
}

int main(void)
{
	const DWORD TestIterations = 100000;
	BYTE Buffer[16384];
	DWORD MaxBufferSize = sizeof(Buffer);
	memset(Buffer, 0, MaxBufferSize);

	// -------------------------------------------------------------------------

	// verify the timer
	DOUBLE StartTime = GetTime();
	Sleep(1000);
	printf("Veryfing timer precision; result should be close to 1.0, got %f\n", GetTime() - StartTime);

	// -------------------------------------------------------------------------

	// prepare RtlGenRandom
	if (PrepareRtlGenRandom()) {
		return 1;
	}

	// -------------------------------------------------------------------------
	// test various buffer sizes

	printf("TestIterations: %lu\n", TestIterations);
	for (DWORD BufferSize = 1; BufferSize <= MaxBufferSize; BufferSize *= 2) {
		if (RunSingleTest(Buffer, BufferSize, TestIterations)) {
			return 1;
		}
	}
}
neolit123 added a commit to neolit123/go that referenced this issue May 9, 2020
The existing function that is used is CryptGenRandom. This function
and the whole underling API is deprecated.

Use the function BCryptGenRandom from the new recommended
API called "Cryptography API: Next Generation (CNG)".

Preload and use the BCRYPT_RNG_ALGORITHM provider.
It follows the standards: FIPS 186-2, FIPS 140-2, NIST SP 800-90

Fixes golang#33542
@alexbrainman
Copy link
Member

@alexbrainman alexbrainman commented May 10, 2020

@alexbrainman hello, when is the deadline for one of the changes to merge with respect to the golang 1.15 release cycle?

I think deadline for 1.15 is already past. Perhaps it is OK to finish existing CL. I do not know. @ianlancetaylor asked on PS3 of https://go-review.googlesource.com/c/go/+/210057/

Filippo, Jason, any interest in trying to get this into 1.15? Needs to be soon.

Perhaps it is OK to resolve this issue for 1.15.

on Monday, i can try asking someone from the Microsoft cryptography team to add an up-to-date comment here to facilitate your mediation.

I am not the one who will decide. I don't consider myself a security expert. I will let others decide.

Alex

neolit123 added a commit to neolit123/go that referenced this issue May 10, 2020
The existing function that is used is CryptGenRandom. This function
and the whole underling API is deprecated.

Use the function BCryptGenRandom from the new recommended
API called "Cryptography API: Next Generation (CNG)".

Preload and use the BCRYPT_RNG_ALGORITHM provider.
It follows the standards: FIPS 186-2, FIPS 140-2, NIST SP 800-90

Fixes golang#33542
neolit123 added a commit to neolit123/go that referenced this issue Sep 6, 2020
The existing function that is used is CryptGenRandom. This function
and the whole underling API is deprecated.

Use the function BCryptGenRandom from the new recommended
API called "Cryptography API: Next Generation (CNG)".

Preload and use the BCRYPT_RNG_ALGORITHM provider.
It follows the standards: FIPS 186-2, FIPS 140-2, NIST SP 800-90

Fixes golang#33542
@FiloSottile
Copy link
Member

@FiloSottile FiloSottile commented Oct 24, 2020

Looks like BoringSSL, Chromium, Firefox, and Rust all use RtlGenRandom unless they are targeting the UWP, and indeed we seem to understand it better than BCryptGenRandom, let's stick with that.

@gopherbot gopherbot closed this in 333e904 Oct 27, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

You can’t perform that action at this time.