Mask generation function

Overview

A Mask Generation Function (MGF) is a cryptographic primitive similar to a Cryptographic hash function except that while a hash function's output is a fixed size, a MGF supports output of a variable length. In this respect, a MGF can be viewed as a single-use Sponge function, it can absorb any length of input and process it to produce any length of output. Mask Generation Functions are completely deterministic. For any given input and desired output length the output is always the same.

Definition

 "A mask generation function takes an octet string of variable length
  and a desired output length as input, and outputs an octet string of
  the desired length. There may be restrictions on the length of the
  input and output octet strings, but such bounds are generally very
  large. Mask generation functions are deterministic; the octet string
  output is completely determined by the input octet string. The output
  of a mask generation function should be pseudorandom, that is, if the
  seed to the function is unknown, it should be infeasible to
  distinguish the output from a truly random string. The plaintext-
  awareness of RSAES-OAEP relies on the random nature of the output of
  the mask generation function, which in turn relies on the random
  nature of the underlying hash." 

Applications

Mask Generation Functions, as generalizations of hash functions, are useful in all the same cases hash functions are useful. However use of a MGF is desirable in cases where a fixed-size hash would be inadequate. Examples include generating padding, one time pads or other forms of symmetric key encryption, or as the basis of a Pseudorandom number generator.

Padding Schemes

Mask Generation Functions were first proposed as part of the specification for passing in the RSA-OAEP algorithm. The OAEP algorithm required a cryptographic hash function that could generate an output equal in size to a "data block" whose length to an arbitrarily sized input message.

Keyed Encryption

The Salsa20 stream cipher may be viewed as a Mask Generation Function as its keystream is produced by hashing the key and nonce with a counter, to yield an arbitrarily long output.

  "Salsa20 expands a 256-bit key and a 64-bit nonce (unique message number) into
a 270-byte stream. It encrypts a b-byte plaintext by xor’ing the plaintext with
the first b bytes of the stream and discarding the rest of the stream. It decrypts
a b-byte ciphertext by xor’ing the ciphertext with the first b bytes of the stream.

  There is no feedback from the plaintext or ciphertext into the stream.
Salsa20 generates the stream in 64-byte (512-bit) blocks. Each block is an
independent hash of the key, the nonce, and a 64-bit block number; there is no
chaining from one block to the next. The Salsa20 output stream can therefore
be accessed randomly, and any number of blocks can be computed in parallel."

Random Number Generators

The NIST Special Publication 800-90A defines a class of cryptographically secure random number generators, one of which is the "Hash DRBG" which uses a hash function with a counter to produce a requested sequence of random bits equal in size to the requested number of random bits.

Examples

Perhaps the most common and straight forward mechanism to build a MGF is to iteratively apply a hash function together with an incrementing counter value. The counter may be incremented indefinitely to yield new output blocks until a sufficient amount of output is collected. This is the approach used in MGF1 shown below.

MGF1

MGF1 is a Mask Generation Function defined in the Public Key Cryptography Standard #1 published by RSA Labroatories.

   Hash    hash function (hLen denotes the length in octets of the hash
           function output)

   Input:
   Z       seed from which mask is generated, an octet string
   l       intended length in octets of the mask, at most 2^32(hLen)

   Output:
   mask    mask, an octet string of length l; or "mask too long"

   Steps:

   1.If l > 2^32(hLen), output "mask too long" and stop.

   2.Let T  be the empty octet string.

   3.For counter from 0 to \lceil{l / hLen}\rceil-1, do the following:

   a.Convert counter to an octet string C of length 4 with the primitive
   I2OSP: C = I2OSP (counter, 4)

   b.Concatenate the hash of the seed Z and C to the octet string T: T =
   T || Hash (Z || C)

   4.Output the leading l octets of T as the octet string mask.

Example Code

Below is the python code implementing MGF1:

import hashlib

def i2osp(integer, size=4):
  return ''.join([chr((integer >> (8 * i)) & 0xFF) for i in reversed(range(size))])

def mgf1(input, length, digest=hashlib.sha1):
  counter = 0
  output = ''
  while (len(output) < length):
    C = i2osp(counter, 4)
    output += digest(input + C).digest()
    counter += 1
  return output[:length]

Sample output from MGF1 using SHA1 as the digest:

Python 2.7.6 (default, Sep  9 2014, 15:04:36) 
[GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.39)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from mgf1 import mgf1
>>> from binascii import hexlify
>>> from hashlib import sha256
>>> print hexlify(mgf1('foo', 3))
1ac907
>>> print hexlify(mgf1('foo', 5))
1ac9075cd4
>>> print hexlify(mgf1('bar', 5))
bc0c655e01
>>> print hexlify(mgf1('bar', 50))
bc0c655e016bc2931d85a2e675181adcef7f581f76df2739da74faac41627be2f7f415c89e983fd0ce80ced9878641cb4876
>>> print hexlify(mgf1('bar', 50, sha256))
382576a7841021cc28fc4c0948753fb8312090cea942ea4c4e735d10dc724b155f9f6069f289d61daca0cb814502ef04eae1