Merge "Fix entropy problems with OS::Random::String" into stable/ocata

4 files changed, 257 insertions, 81 deletions

diff --git a/heat/common/password_gen.py b/heat/common/password_gen.py
new file mode 100644
index 000000000..93b03c6b9
--- /dev/null
+++ b/heat/common/password_gen.py
@@ -0,0 +1,109 @@
+#
+#    Licensed under the Apache License, Version 2.0 (the "License"); you may
+#    not use this file except in compliance with the License. You may obtain
+#    a copy of the License at
+#
+#         http://www.apache.org/licenses/LICENSE-2.0
+#
+#    Unless required by applicable law or agreed to in writing, software
+#    distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+#    WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+#    License for the specific language governing permissions and limitations
+#    under the License.
+
+import collections
+import random as random_module
+import string
+
+import six
+
+
+# NOTE(pas-ha) Heat officially supports only POSIX::Linux platform
+# where os.urandom() and random.SystemRandom() are available
+random = random_module.SystemRandom()
+
+
+CHARACTER_CLASSES = (
+    LETTERS_DIGITS, LETTERS, LOWERCASE, UPPERCASE,
+    DIGITS, HEXDIGITS, OCTDIGITS,
+) = (
+    'lettersdigits', 'letters', 'lowercase', 'uppercase',
+    'digits', 'hexdigits', 'octdigits',
+)
+
+_char_class_members = {
+    LETTERS_DIGITS: string.ascii_letters + string.digits,
+    LETTERS: string.ascii_letters,
+    LOWERCASE: string.ascii_lowercase,
+    UPPERCASE: string.ascii_uppercase,
+    DIGITS: string.digits,
+    HEXDIGITS: string.digits + 'ABCDEF',
+    OCTDIGITS: string.octdigits,
+}
+
+
+CharClass = collections.namedtuple('CharClass',
+                                   ('allowed_chars', 'min_count'))
+
+
+def named_char_class(char_class, min_count=0):
+    """Return a predefined character class.
+
+    The result of this function can be passed to :func:`generate_password` as
+    one of the character classes to use in generating a password.
+
+    :param char_class: Any of the character classes named in
+                       :const:`CHARACTER_CLASSES`
+    :param min_count: The minimum number of members of this class to appear in
+                      a generated password
+    """
+    assert char_class in CHARACTER_CLASSES
+    return CharClass(frozenset(_char_class_members[char_class]), min_count)
+
+
+def special_char_class(allowed_chars, min_count=0):
+    """Return a character class containing custom characters.
+
+    The result of this function can be passed to :func:`generate_password` as
+    one of the character classes to use in generating a password.
+
+    :param allowed_chars: Iterable of the characters in the character class
+    :param min_count: The minimum number of members of this class to appear in
+                      a generated password
+    """
+    return CharClass(frozenset(allowed_chars), min_count)
+
+
+def generate_password(length, char_classes):
+    """Generate a random password.
+
+    The password will be of the specified length, and comprised of characters
+    from the specified character classes, which can be generated using the
+    :func:`named_char_class` and :func:`special_char_class` functions. Where
+    a minimum count is specified in the character class, at least that number
+    of characters in the resulting password are guaranteed to be from that
+    character class.
+
+    :param length: The length of the password to generate, in characters
+    :param char_classes: Iterable over classes of characters from which to
+                         generate a password
+    """
+    char_buffer = six.StringIO()
+    all_allowed_chars = set()
+
+    # Add the minimum number of chars from each char class
+    for char_class in char_classes:
+        all_allowed_chars |= char_class.allowed_chars
+        allowed_chars = tuple(char_class.allowed_chars)
+        for i in six.moves.xrange(char_class.min_count):
+            char_buffer.write(random.choice(allowed_chars))
+
+    # Fill up rest with random chars from provided classes
+    combined_chars = tuple(all_allowed_chars)
+    for i in six.moves.xrange(max(0, length - char_buffer.tell())):
+        char_buffer.write(random.choice(combined_chars))
+
+    # Shuffle string
+    selected_chars = char_buffer.getvalue()
+    char_buffer.close()
+    return ''.join(random.sample(selected_chars, length))
diff --git a/heat/engine/resources/openstack/heat/random_string.py b/heat/engine/resources/openstack/heat/random_string.py
index 9052b5062..9c457a936 100644
--- a/heat/engine/resources/openstack/heat/random_string.py
+++ b/heat/engine/resources/openstack/heat/random_string.py
@@ -11,13 +11,11 @@
 #    License for the specific language governing permissions and limitations
 #    under the License.
 
-import random as random_module
-import string
-
 import six
 
 from heat.common import exception
 from heat.common.i18n import _
+from heat.common import password_gen
 from heat.engine import attributes
 from heat.engine import constraints
 from heat.engine import properties
@@ -25,10 +23,6 @@ from heat.engine import resource
 from heat.engine import support
 from heat.engine import translation
 
-# NOTE(pas-ha) Heat officially supports only POSIX::Linux platform
-# where os.urandom() and random.SystemRandom() are available
-random = random_module.SystemRandom()
-
 
 class RandomString(resource.Resource):
     """A resource which generates a random string.
@@ -83,10 +77,7 @@ class RandomString(resource.Resource):
             properties.Schema.STRING,
             _('Sequence of characters to build the random string from.'),
             constraints=[
-                constraints.AllowedValues(['lettersdigits', 'letters',
-                                           'lowercase', 'uppercase',
-                                           'digits', 'hexdigits',
-                                           'octdigits']),
+                constraints.AllowedValues(password_gen.CHARACTER_CLASSES),
             ],
             support_status=support.SupportStatus(
                 status=support.HIDDEN,
@@ -112,11 +103,9 @@ class RandomString(resource.Resource):
                          % {'min': CHARACTER_CLASSES_MIN}),
                         constraints=[
                             constraints.AllowedValues(
-                                ['lettersdigits', 'letters', 'lowercase',
-                                 'uppercase', 'digits', 'hexdigits',
-                                 'octdigits']),
+                                password_gen.CHARACTER_CLASSES),
                         ],
-                        default='lettersdigits'),
+                        default=password_gen.LETTERS_DIGITS),
                     CHARACTER_CLASSES_MIN: properties.Schema(
                         properties.Schema.INTEGER,
                         _('The minimum number of characters from this '
@@ -130,7 +119,7 @@ class RandomString(resource.Resource):
                 }
             ),
             # add defaults for backward compatibility
-            default=[{CHARACTER_CLASSES_CLASS: 'lettersdigits',
+            default=[{CHARACTER_CLASSES_CLASS: password_gen.LETTERS_DIGITS,
                       CHARACTER_CLASSES_MIN: 1}]
 
         ),
@@ -177,16 +166,6 @@ class RandomString(resource.Resource):
         ),
     }
 
-    _sequences = {
-        'lettersdigits': string.ascii_letters + string.digits,
-        'letters': string.ascii_letters,
-        'lowercase': string.ascii_lowercase,
-        'uppercase': string.ascii_uppercase,
-        'digits': string.digits,
-        'hexdigits': string.digits + 'ABCDEF',
-        'octdigits': string.octdigits
-    }
-
     def translation_rules(self, props):
         if props.get(self.SEQUENCE):
             return [
@@ -205,57 +184,19 @@ class RandomString(resource.Resource):
             ]
 
     def _generate_random_string(self, char_sequences, char_classes, length):
-        random_string = ""
-
-        # Add the minimum number of chars from each char sequence & char class
-        if char_sequences:
-            for char_seq in char_sequences:
-                seq = char_seq[self.CHARACTER_SEQUENCES_SEQUENCE]
-                seq_min = char_seq[self.CHARACTER_SEQUENCES_MIN]
-                for i in six.moves.xrange(seq_min):
-                    random_string += random.choice(seq)
-
-        if char_classes:
-            for char_class in char_classes:
-                cclass_class = char_class[self.CHARACTER_CLASSES_CLASS]
-                cclass_seq = self._sequences[cclass_class]
-                cclass_min = char_class[self.CHARACTER_CLASSES_MIN]
-                for i in six.moves.xrange(cclass_min):
-                    random_string += random.choice(cclass_seq)
-
-        def random_class_char():
-            cclass_dict = random.choice(char_classes)
-            cclass_class = cclass_dict[self.CHARACTER_CLASSES_CLASS]
-            cclass_seq = self._sequences[cclass_class]
-            return random.choice(cclass_seq)
-
-        def random_seq_char():
-            seq_dict = random.choice(char_sequences)
-            seq = seq_dict[self.CHARACTER_SEQUENCES_SEQUENCE]
-            return random.choice(seq)
-
-        # Fill up rest with random chars from provided sequences & classes
-        if char_sequences and char_classes:
-            weighted_choices = ([True] * len(char_classes) +
-                                [False] * len(char_sequences))
-            while len(random_string) < length:
-                if random.choice(weighted_choices):
-                    random_string += random_class_char()
-                else:
-                    random_string += random_seq_char()
-
-        elif char_sequences:
-            while len(random_string) < length:
-                random_string += random_seq_char()
-
-        else:
-            while len(random_string) < length:
-                random_string += random_class_char()
-
-        # Randomize string
-        random_string = ''.join(random.sample(random_string,
-                                              len(random_string)))
-        return random_string
+        seq_mins = [
+            password_gen.special_char_class(
+                char_seq[self.CHARACTER_SEQUENCES_SEQUENCE],
+                char_seq[self.CHARACTER_SEQUENCES_MIN])
+            for char_seq in char_sequences]
+        char_class_mins = [
+            password_gen.named_char_class(
+                char_class[self.CHARACTER_CLASSES_CLASS],
+                char_class[self.CHARACTER_CLASSES_MIN])
+            for char_class in char_classes]
+
+        return password_gen.generate_password(length,
+                                              seq_mins + char_class_mins)
 
     def validate(self):
         super(RandomString, self).validate()
@@ -276,8 +217,8 @@ class RandomString(resource.Resource):
             raise exception.StackValidationFailed(message=msg)
 
     def handle_create(self):
-        char_sequences = self.properties[self.CHARACTER_SEQUENCES]
-        char_classes = self.properties[self.CHARACTER_CLASSES]
+        char_sequences = self.properties[self.CHARACTER_SEQUENCES] or []
+        char_classes = self.properties[self.CHARACTER_CLASSES] or []
         length = self.properties[self.LENGTH]
 
         random_string = self._generate_random_string(char_sequences,
diff --git a/heat/tests/openstack/heat/test_random_string.py b/heat/tests/openstack/heat/test_random_string.py
index 82b45c34a..2748ffcf4 100644
--- a/heat/tests/openstack/heat/test_random_string.py
+++ b/heat/tests/openstack/heat/test_random_string.py
@@ -258,7 +258,7 @@ Resources:
         return stack
 
     # test was saved to test backward compatibility with old behavior
-    def test_generate_random_string_backward_compatiable(self):
+    def test_generate_random_string_backward_compatible(self):
         stack = self.parse_stack(template_format.parse(self.template_rs))
         secret = stack['secret']
         char_classes = secret.properties['character_classes']
@@ -267,8 +267,125 @@ Resources:
         # run each test multiple times to confirm random generator
         # doesn't generate a matching pattern by chance
         for i in range(1, 32):
-            r = secret._generate_random_string(None, char_classes, self.length)
+            r = secret._generate_random_string([], char_classes, self.length)
 
             self.assertThat(r, matchers.HasLength(self.length))
             regex = '%s{%s}' % (self.pattern, self.length)
             self.assertThat(r, matchers.MatchesRegex(regex))
+
+
+class TestGenerateRandomStringDistribution(common.HeatTestCase):
+    def run_test(self, tmpl, iterations=5):
+        stack = utils.parse_stack(template_format.parse(tmpl))
+        secret = stack['secret']
+        secret.data_set = mock.Mock()
+
+        for i in range(iterations):
+            secret.handle_create()
+
+        return [call[1][1] for call in secret.data_set.mock_calls]
+
+    def char_counts(self, random_strings, char):
+        return [rs.count(char) for rs in random_strings]
+
+    def check_stats(self, char_counts, expected_mean, allowed_variance,
+                    expected_minimum=0):
+        mean = float(sum(char_counts)) / len(char_counts)
+        self.assertLess(mean, expected_mean + allowed_variance)
+        self.assertGreater(mean, max(0, expected_mean - allowed_variance))
+        if expected_minimum:
+            self.assertGreaterEqual(min(char_counts), expected_minimum)
+
+    def test_class_uniformity(self):
+        template_rs = '''
+HeatTemplateFormatVersion: '2012-12-12'
+Resources:
+  secret:
+    Type: OS::Heat::RandomString
+    Properties:
+      length: 66
+      character_classes:
+        - class: lettersdigits
+      character_sequences:
+        - sequence: "*$"
+'''
+
+        results = self.run_test(template_rs, 10)
+        for char in '$*':
+            self.check_stats(self.char_counts(results, char), 1.5, 2)
+
+    def test_repeated_sequence(self):
+        template_rs = '''
+HeatTemplateFormatVersion: '2012-12-12'
+Resources:
+  secret:
+    Type: OS::Heat::RandomString
+    Properties:
+      length: 40
+      character_classes: []
+      character_sequences:
+        - sequence: "**********$*****************************"
+'''
+
+        results = self.run_test(template_rs)
+        for char in '$*':
+            self.check_stats(self.char_counts(results, char), 20, 6)
+
+    def test_overlapping_classes(self):
+        template_rs = '''
+HeatTemplateFormatVersion: '2012-12-12'
+Resources:
+  secret:
+    Type: OS::Heat::RandomString
+    Properties:
+      length: 624
+      character_classes:
+        - class: lettersdigits
+        - class: digits
+        - class: octdigits
+        - class: hexdigits
+'''
+
+        results = self.run_test(template_rs, 20)
+        self.check_stats(self.char_counts(results, '0'), 10.3, 2.5)
+
+    def test_overlapping_sequences(self):
+        template_rs = '''
+HeatTemplateFormatVersion: '2012-12-12'
+Resources:
+  secret:
+    Type: OS::Heat::RandomString
+    Properties:
+      length: 60
+      character_classes: []
+      character_sequences:
+        - sequence: "01"
+        - sequence: "02"
+        - sequence: "03"
+        - sequence: "04"
+        - sequence: "05"
+        - sequence: "06"
+        - sequence: "07"
+        - sequence: "08"
+        - sequence: "09"
+'''
+
+        results = self.run_test(template_rs)
+        self.check_stats(self.char_counts(results, '0'), 10, 5)
+
+    def test_overlapping_class_sequence(self):
+        template_rs = '''
+HeatTemplateFormatVersion: '2012-12-12'
+Resources:
+  secret:
+    Type: OS::Heat::RandomString
+    Properties:
+      length: 402
+      character_classes:
+        - class: octdigits
+      character_sequences:
+        - sequence: "0"
+'''
+
+        results = self.run_test(template_rs, 10)
+        self.check_stats(self.char_counts(results, '0'), 51.125, 8, 1)
diff --git a/releasenotes/notes/random-string-entropy-9b8e23874cd79b8f.yaml b/releasenotes/notes/random-string-entropy-9b8e23874cd79b8f.yaml
new file mode 100644
index 000000000..a796fd944
--- /dev/null
+++ b/releasenotes/notes/random-string-entropy-9b8e23874cd79b8f.yaml
@@ -0,0 +1,9 @@
+---
+security:
+  - |
+    Passwords generated by the OS::Heat::RandomString resource may have had
+    less entropy than expected, depending on what is specified in the
+    ``character_class`` and ``character_sequence`` properties. This has been
+    corrected so that each character present in any of the specified classes
+    or sequences now has an equal probability of appearing at each point in
+    the generated random string.