RandomString may have less entropy than expected

[Zane Bitter]

When generating a random string, once we have selected from the various required pools, we continue by selecting a pool at random and then selecting a character from that pool at random. This does not take into account the differing sizes of the available pools, nor the fact that the same character could appear in multiple pools. This results in a non-uniform probability distribution of characters.

For example, in the following resource:

    type: OS::Heat::RandomString
    properties:
      length: 66
      character_classes:
        - class: lettersdigits
      character_sequences:
        - sequence: "*$"

one might reasonably expect to find an average of 3 '*' or '$' characters in the output, but in fact there would be an average of 33.

Since users mostly make use of this feature to generate default passwords for services they are deploying, this would result in the generated passwords having slightly less entropy than expected. Pathological cases where the entropy is massively reduced (like the one above - where it is only 229.5 bits vs. the expected 391 bits) are possible, although it's probably unlikely that users would encounter them by accident.

[OpenStack Infra (hudson-openstack)]

Fix proposed to branch: master
Review: https://review.openstack.org/554745

[Tristan Cacqueray (tristan-cacqueray)]

Since this report concerns a possible security risk, an incomplete security advisory task has been added while the core security reviewers for the affected project or projects confirm the bug and discuss the scope of any vulnerability along with potential solutions.

[Tristan Cacqueray (tristan-cacqueray)]

That might be an issue for smaller password length. Is the algorithm still takes into account the "min" attribute of character_classes/character_sequences property?

[Jeremy Stanley (fungi)]

If this is going to be backported to supported stable branches we could consider issuing an advisory, but even though a 40% strength reduction seems significant the actual brute-force difference between a 229.5-bit and 391-bit secret is going to be purely academic in a vast majority of real-world cases.

[Zane Bitter (zaneb)]

Yeah, it's likely only a problem if you (a) set up the character_sequences in strange ways, *and* (b) choose a relatively short password length. (If you have a password length of 66 this is obviously a non-issue - I lifted that example from the test case I wrote, where I chose it because the math worked out easily :)

The "min" properties are correctly taken into account, so no issues there. It's selecting everything else once you've fulfilled the minimum counts that's a problem.

[Tristan Cacqueray (tristan-cacqueray)]

Thanks for the prompt feedback. I suggest we triage this bug as C1 or even D according to VMT taxonomy ( https://security.openstack.org/vmt-process.html#incident-report-taxonomy ).

[Jeremy Stanley (fungi)]

Yeah, seems like a security hardening opportunity. Probably still worth backporting to supported stable branches if it can be done trivially/unobtrusively without causing backward-incompatibilities but I wouldn't press for any advisory on this one.

[Zane Bitter (zaneb)]

Ack, I would concur with that (Class D). The patch is not tiny, but it is very localised so I don't see any obstacles to backporting.

[Jeremy Stanley (fungi)]

Thanks. In that case I'll just flag it as a security hardening opportunity. We can revisit that and issue an advisory if new issues come to light suggesting it's more serious than we think.

[OpenStack Infra (hudson-openstack)]

Reviewed: https://review.openstack.org/554745
Committed: https://git.openstack.org/cgit/openstack/heat/commit/?id=6e16c051ba9c2fc409c82fda19467d9ee1aaf484
Submitter: Zuul
Branch: master

commit 6e16c051ba9c2fc409c82fda19467d9ee1aaf484
Author: Zane Bitter <email address hidden>
Date: Tue Mar 20 20:48:38 2018 -0400

    Fix entropy problems with OS::Random::String

    When generating a random string, once we had selected from the various
    required pools, we continued by selecting a pool at random and then
    selecting a character from that pool at random. This did not take into
    account the differing sizes of the available pools, nor the fact that the
    same character could appear in multiple pools, which resulted in a
    non-uniform probability distribution of characters. Since users mostly make
    use of this feature to generate default passwords for services they are
    deploying, this would result in the generated passwords having slightly
    less entropy than expected (and pathological cases were possible).

    Rectify this by always selecting non-constrained characters from a single
    combined pool, and by ensuring that each character appears only once in any
    pool we're selecting from.

    Since we also want to use this method to generate passwords for OpenStack
    Users, the new implementation is in a separate module in heat.common rather
    than mixed in with the resource's logic. Also, use a StringIO object to
    collect the characters rather than repeatedly appending to a string.

    Change-Id: Ia7b63e72c1e3c0649290caf4fea8a32f7f89560b
    Closes-Bug: #1757300
    Related-Bug: #1666129
    Related-Bug: #1444429

[OpenStack Infra (hudson-openstack)]

Fix proposed to branch: stable/queens
Review: https://review.openstack.org/555859

[OpenStack Infra (hudson-openstack)]

Fix proposed to branch: stable/pike
Review: https://review.openstack.org/555905

[OpenStack Infra (hudson-openstack)]

Reviewed: https://review.openstack.org/555859
Committed: https://git.openstack.org/cgit/openstack/heat/commit/?id=8437ec3fce1fe742cceadb10982ab870dceb0e98
Submitter: Zuul
Branch: stable/queens

commit 8437ec3fce1fe742cceadb10982ab870dceb0e98
Author: Zane Bitter <email address hidden>
Date: Tue Mar 20 20:48:38 2018 -0400

    Fix entropy problems with OS::Random::String

    When generating a random string, once we had selected from the various
    required pools, we continued by selecting a pool at random and then
    selecting a character from that pool at random. This did not take into
    account the differing sizes of the available pools, nor the fact that the
    same character could appear in multiple pools, which resulted in a
    non-uniform probability distribution of characters. Since users mostly make
    use of this feature to generate default passwords for services they are
    deploying, this would result in the generated passwords having slightly
    less entropy than expected (and pathological cases were possible).

    Rectify this by always selecting non-constrained characters from a single
    combined pool, and by ensuring that each character appears only once in any
    pool we're selecting from.

    Since we also want to use this method to generate passwords for OpenStack
    Users, the new implementation is in a separate module in heat.common rather
    than mixed in with the resource's logic. Also, use a StringIO object to
    collect the characters rather than repeatedly appending to a string.

    Change-Id: Ia7b63e72c1e3c0649290caf4fea8a32f7f89560b
    Closes-Bug: #1757300
    Related-Bug: #1666129
    Related-Bug: #1444429
    (cherry picked from commit 6e16c051ba9c2fc409c82fda19467d9ee1aaf484)

[OpenStack Infra (hudson-openstack)]

Fix proposed to branch: stable/ocata
Review: https://review.openstack.org/559188

[OpenStack Infra (hudson-openstack)]

Reviewed: https://review.openstack.org/555905
Committed: https://git.openstack.org/cgit/openstack/heat/commit/?id=a08893dc865ab5fd39c013fe727f7cbf267583ad
Submitter: Zuul
Branch: stable/pike

commit a08893dc865ab5fd39c013fe727f7cbf267583ad
Author: Zane Bitter <email address hidden>
Date: Tue Mar 20 20:48:38 2018 -0400

    Fix entropy problems with OS::Random::String

    When generating a random string, once we had selected from the various
    required pools, we continued by selecting a pool at random and then
    selecting a character from that pool at random. This did not take into
    account the differing sizes of the available pools, nor the fact that the
    same character could appear in multiple pools, which resulted in a
    non-uniform probability distribution of characters. Since users mostly make
    use of this feature to generate default passwords for services they are
    deploying, this would result in the generated passwords having slightly
    less entropy than expected (and pathological cases were possible).

    Rectify this by always selecting non-constrained characters from a single
    combined pool, and by ensuring that each character appears only once in any
    pool we're selecting from.

    Since we also want to use this method to generate passwords for OpenStack
    Users, the new implementation is in a separate module in heat.common rather
    than mixed in with the resource's logic. Also, use a StringIO object to
    collect the characters rather than repeatedly appending to a string.

    Change-Id: Ia7b63e72c1e3c0649290caf4fea8a32f7f89560b
    Closes-Bug: #1757300
    Related-Bug: #1666129
    Related-Bug: #1444429
    (cherry picked from commit 6e16c051ba9c2fc409c82fda19467d9ee1aaf484)

[OpenStack Infra (hudson-openstack)]

This issue was fixed in the openstack/heat 11.0.0.0b1 development milestone.

[OpenStack Infra (hudson-openstack)]

This issue was fixed in the openstack/heat 10.0.1 release.

[OpenStack Infra (hudson-openstack)]

Reviewed: https://review.openstack.org/559188
Committed: https://git.openstack.org/cgit/openstack/heat/commit/?id=8ce005cc0e309938f9d0fbdae65c92a406348936
Submitter: Zuul
Branch: stable/ocata

commit 8ce005cc0e309938f9d0fbdae65c92a406348936
Author: Zane Bitter <email address hidden>
Date: Tue Mar 20 20:48:38 2018 -0400

    Fix entropy problems with OS::Random::String

    When generating a random string, once we had selected from the various
    required pools, we continued by selecting a pool at random and then
    selecting a character from that pool at random. This did not take into
    account the differing sizes of the available pools, nor the fact that the
    same character could appear in multiple pools, which resulted in a
    non-uniform probability distribution of characters. Since users mostly make
    use of this feature to generate default passwords for services they are
    deploying, this would result in the generated passwords having slightly
    less entropy than expected (and pathological cases were possible).

    Rectify this by always selecting non-constrained characters from a single
    combined pool, and by ensuring that each character appears only once in any
    pool we're selecting from.

    Since we also want to use this method to generate passwords for OpenStack
    Users, the new implementation is in a separate module in heat.common rather
    than mixed in with the resource's logic. Also, use a StringIO object to
    collect the characters rather than repeatedly appending to a string.

    Change-Id: Ia7b63e72c1e3c0649290caf4fea8a32f7f89560b
    Closes-Bug: #1757300
    Related-Bug: #1666129
    Related-Bug: #1444429
    (cherry picked from commit 6e16c051ba9c2fc409c82fda19467d9ee1aaf484)

[OpenStack Infra (hudson-openstack)]

This issue was fixed in the openstack/heat 8.0.7 release.

[OpenStack Infra (hudson-openstack)]

This issue was fixed in the openstack/heat 9.0.5 release.