DSS.py 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403
  1. #
  2. # Signature/DSS.py : DSS.py
  3. #
  4. # ===================================================================
  5. #
  6. # Copyright (c) 2014, Legrandin <helderijs@gmail.com>
  7. # All rights reserved.
  8. #
  9. # Redistribution and use in source and binary forms, with or without
  10. # modification, are permitted provided that the following conditions
  11. # are met:
  12. #
  13. # 1. Redistributions of source code must retain the above copyright
  14. # notice, this list of conditions and the following disclaimer.
  15. # 2. Redistributions in binary form must reproduce the above copyright
  16. # notice, this list of conditions and the following disclaimer in
  17. # the documentation and/or other materials provided with the
  18. # distribution.
  19. #
  20. # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21. # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22. # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  23. # FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  24. # COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  25. # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  26. # BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  27. # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  28. # CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29. # LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  30. # ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31. # POSSIBILITY OF SUCH DAMAGE.
  32. # ===================================================================
  33. from Crypto.Util.asn1 import DerSequence
  34. from Crypto.Util.number import long_to_bytes
  35. from Crypto.Math.Numbers import Integer
  36. from Crypto.Hash import HMAC
  37. from Crypto.PublicKey.ECC import EccKey
  38. from Crypto.PublicKey.DSA import DsaKey
  39. __all__ = ['DssSigScheme', 'new']
  40. class DssSigScheme(object):
  41. """A (EC)DSA signature object.
  42. Do not instantiate directly.
  43. Use :func:`Crypto.Signature.DSS.new`.
  44. """
  45. def __init__(self, key, encoding, order):
  46. """Create a new Digital Signature Standard (DSS) object.
  47. Do not instantiate this object directly,
  48. use `Crypto.Signature.DSS.new` instead.
  49. """
  50. self._key = key
  51. self._encoding = encoding
  52. self._order = order
  53. self._order_bits = self._order.size_in_bits()
  54. self._order_bytes = (self._order_bits - 1) // 8 + 1
  55. def can_sign(self):
  56. """Return ``True`` if this signature object can be used
  57. for signing messages."""
  58. return self._key.has_private()
  59. def _compute_nonce(self, msg_hash):
  60. raise NotImplementedError("To be provided by subclasses")
  61. def _valid_hash(self, msg_hash):
  62. raise NotImplementedError("To be provided by subclasses")
  63. def sign(self, msg_hash):
  64. """Compute the DSA/ECDSA signature of a message.
  65. Args:
  66. msg_hash (hash object):
  67. The hash that was carried out over the message.
  68. The object belongs to the :mod:`Crypto.Hash` package.
  69. Under mode ``'fips-186-3'``, the hash must be a FIPS
  70. approved secure hash (SHA-2 or SHA-3).
  71. :return: The signature as ``bytes``
  72. :raise ValueError: if the hash algorithm is incompatible to the (EC)DSA key
  73. :raise TypeError: if the (EC)DSA key has no private half
  74. """
  75. if not self._key.has_private():
  76. raise TypeError("Private key is needed to sign")
  77. if not self._valid_hash(msg_hash):
  78. raise ValueError("Hash is not sufficiently strong")
  79. # Generate the nonce k (critical!)
  80. nonce = self._compute_nonce(msg_hash)
  81. # Perform signature using the raw API
  82. z = Integer.from_bytes(msg_hash.digest()[:self._order_bytes])
  83. sig_pair = self._key._sign(z, nonce)
  84. # Encode the signature into a single byte string
  85. if self._encoding == 'binary':
  86. output = b"".join([long_to_bytes(x, self._order_bytes)
  87. for x in sig_pair])
  88. else:
  89. # Dss-sig ::= SEQUENCE {
  90. # r INTEGER,
  91. # s INTEGER
  92. # }
  93. # Ecdsa-Sig-Value ::= SEQUENCE {
  94. # r INTEGER,
  95. # s INTEGER
  96. # }
  97. output = DerSequence(sig_pair).encode()
  98. return output
  99. def verify(self, msg_hash, signature):
  100. """Check if a certain (EC)DSA signature is authentic.
  101. Args:
  102. msg_hash (hash object):
  103. The hash that was carried out over the message.
  104. This is an object belonging to the :mod:`Crypto.Hash` module.
  105. Under mode ``'fips-186-3'``, the hash must be a FIPS
  106. approved secure hash (SHA-2 or SHA-3).
  107. signature (``bytes``):
  108. The signature that needs to be validated.
  109. :raise ValueError: if the signature is not authentic
  110. """
  111. if not self._valid_hash(msg_hash):
  112. raise ValueError("Hash is not sufficiently strong")
  113. if self._encoding == 'binary':
  114. if len(signature) != (2 * self._order_bytes):
  115. raise ValueError("The signature is not authentic (length)")
  116. r_prime, s_prime = [Integer.from_bytes(x)
  117. for x in (signature[:self._order_bytes],
  118. signature[self._order_bytes:])]
  119. else:
  120. try:
  121. der_seq = DerSequence().decode(signature, strict=True)
  122. except (ValueError, IndexError):
  123. raise ValueError("The signature is not authentic (DER)")
  124. if len(der_seq) != 2 or not der_seq.hasOnlyInts():
  125. raise ValueError("The signature is not authentic (DER content)")
  126. r_prime, s_prime = Integer(der_seq[0]), Integer(der_seq[1])
  127. if not (0 < r_prime < self._order) or not (0 < s_prime < self._order):
  128. raise ValueError("The signature is not authentic (d)")
  129. z = Integer.from_bytes(msg_hash.digest()[:self._order_bytes])
  130. result = self._key._verify(z, (r_prime, s_prime))
  131. if not result:
  132. raise ValueError("The signature is not authentic")
  133. # Make PyCrypto code to fail
  134. return False
  135. class DeterministicDsaSigScheme(DssSigScheme):
  136. # Also applicable to ECDSA
  137. def __init__(self, key, encoding, order, private_key):
  138. super(DeterministicDsaSigScheme, self).__init__(key, encoding, order)
  139. self._private_key = private_key
  140. def _bits2int(self, bstr):
  141. """See 2.3.2 in RFC6979"""
  142. result = Integer.from_bytes(bstr)
  143. q_len = self._order.size_in_bits()
  144. b_len = len(bstr) * 8
  145. if b_len > q_len:
  146. # Only keep leftmost q_len bits
  147. result >>= (b_len - q_len)
  148. return result
  149. def _int2octets(self, int_mod_q):
  150. """See 2.3.3 in RFC6979"""
  151. assert 0 < int_mod_q < self._order
  152. return long_to_bytes(int_mod_q, self._order_bytes)
  153. def _bits2octets(self, bstr):
  154. """See 2.3.4 in RFC6979"""
  155. z1 = self._bits2int(bstr)
  156. if z1 < self._order:
  157. z2 = z1
  158. else:
  159. z2 = z1 - self._order
  160. return self._int2octets(z2)
  161. def _compute_nonce(self, mhash):
  162. """Generate k in a deterministic way"""
  163. # See section 3.2 in RFC6979.txt
  164. # Step a
  165. h1 = mhash.digest()
  166. # Step b
  167. mask_v = b'\x01' * mhash.digest_size
  168. # Step c
  169. nonce_k = b'\x00' * mhash.digest_size
  170. for int_oct in (b'\x00', b'\x01'):
  171. # Step d/f
  172. nonce_k = HMAC.new(nonce_k,
  173. mask_v + int_oct +
  174. self._int2octets(self._private_key) +
  175. self._bits2octets(h1), mhash).digest()
  176. # Step e/g
  177. mask_v = HMAC.new(nonce_k, mask_v, mhash).digest()
  178. nonce = -1
  179. while not (0 < nonce < self._order):
  180. # Step h.C (second part)
  181. if nonce != -1:
  182. nonce_k = HMAC.new(nonce_k, mask_v + b'\x00',
  183. mhash).digest()
  184. mask_v = HMAC.new(nonce_k, mask_v, mhash).digest()
  185. # Step h.A
  186. mask_t = b""
  187. # Step h.B
  188. while len(mask_t) < self._order_bytes:
  189. mask_v = HMAC.new(nonce_k, mask_v, mhash).digest()
  190. mask_t += mask_v
  191. # Step h.C (first part)
  192. nonce = self._bits2int(mask_t)
  193. return nonce
  194. def _valid_hash(self, msg_hash):
  195. return True
  196. class FipsDsaSigScheme(DssSigScheme):
  197. #: List of L (bit length of p) and N (bit length of q) combinations
  198. #: that are allowed by FIPS 186-3. The security level is provided in
  199. #: Table 2 of FIPS 800-57 (rev3).
  200. _fips_186_3_L_N = (
  201. (1024, 160), # 80 bits (SHA-1 or stronger)
  202. (2048, 224), # 112 bits (SHA-224 or stronger)
  203. (2048, 256), # 128 bits (SHA-256 or stronger)
  204. (3072, 256) # 256 bits (SHA-512)
  205. )
  206. def __init__(self, key, encoding, order, randfunc):
  207. super(FipsDsaSigScheme, self).__init__(key, encoding, order)
  208. self._randfunc = randfunc
  209. L = Integer(key.p).size_in_bits()
  210. if (L, self._order_bits) not in self._fips_186_3_L_N:
  211. error = ("L/N (%d, %d) is not compliant to FIPS 186-3"
  212. % (L, self._order_bits))
  213. raise ValueError(error)
  214. def _compute_nonce(self, msg_hash):
  215. # hash is not used
  216. return Integer.random_range(min_inclusive=1,
  217. max_exclusive=self._order,
  218. randfunc=self._randfunc)
  219. def _valid_hash(self, msg_hash):
  220. """Verify that SHA-1, SHA-2 or SHA-3 are used"""
  221. return (msg_hash.oid == "1.3.14.3.2.26" or
  222. msg_hash.oid.startswith("2.16.840.1.101.3.4.2."))
  223. class FipsEcDsaSigScheme(DssSigScheme):
  224. def __init__(self, key, encoding, order, randfunc):
  225. super(FipsEcDsaSigScheme, self).__init__(key, encoding, order)
  226. self._randfunc = randfunc
  227. def _compute_nonce(self, msg_hash):
  228. return Integer.random_range(min_inclusive=1,
  229. max_exclusive=self._key._curve.order,
  230. randfunc=self._randfunc)
  231. def _valid_hash(self, msg_hash):
  232. """Verify that the strength of the hash matches or exceeds
  233. the strength of the EC. We fail if the hash is too weak."""
  234. modulus_bits = self._key.pointQ.size_in_bits()
  235. # SHS: SHA-2, SHA-3, truncated SHA-512
  236. sha224 = ("2.16.840.1.101.3.4.2.4", "2.16.840.1.101.3.4.2.7", "2.16.840.1.101.3.4.2.5")
  237. sha256 = ("2.16.840.1.101.3.4.2.1", "2.16.840.1.101.3.4.2.8", "2.16.840.1.101.3.4.2.6")
  238. sha384 = ("2.16.840.1.101.3.4.2.2", "2.16.840.1.101.3.4.2.9")
  239. sha512 = ("2.16.840.1.101.3.4.2.3", "2.16.840.1.101.3.4.2.10")
  240. shs = sha224 + sha256 + sha384 + sha512
  241. try:
  242. result = msg_hash.oid in shs
  243. except AttributeError:
  244. result = False
  245. return result
  246. def new(key, mode, encoding='binary', randfunc=None):
  247. """Create a signature object :class:`DssSigScheme` that
  248. can perform (EC)DSA signature or verification.
  249. .. note::
  250. Refer to `NIST SP 800 Part 1 Rev 4`_ (or newer release) for an
  251. overview of the recommended key lengths.
  252. Args:
  253. key (:class:`Crypto.PublicKey.DSA` or :class:`Crypto.PublicKey.ECC`):
  254. The key to use for computing the signature (*private* keys only)
  255. or for verifying one.
  256. For DSA keys, let ``L`` and ``N`` be the bit lengths of the modulus ``p``
  257. and of ``q``: the pair ``(L,N)`` must appear in the following list,
  258. in compliance to section 4.2 of `FIPS 186-4`_:
  259. - (1024, 160) *legacy only; do not create new signatures with this*
  260. - (2048, 224) *deprecated; do not create new signatures with this*
  261. - (2048, 256)
  262. - (3072, 256)
  263. For ECC, only keys over P-224, P-256, P-384, and P-521 are accepted.
  264. mode (string):
  265. The parameter can take these values:
  266. - ``'fips-186-3'``. The signature generation is randomized and carried out
  267. according to `FIPS 186-3`_: the nonce ``k`` is taken from the RNG.
  268. - ``'deterministic-rfc6979'``. The signature generation is not
  269. randomized. See RFC6979_.
  270. encoding (string):
  271. How the signature is encoded. This value determines the output of
  272. :meth:`sign` and the input to :meth:`verify`.
  273. The following values are accepted:
  274. - ``'binary'`` (default), the signature is the raw concatenation
  275. of ``r`` and ``s``. It is defined in the IEEE P.1363 standard.
  276. For DSA, the size in bytes of the signature is ``N/4`` bytes
  277. (e.g. 64 for ``N=256``).
  278. For ECDSA, the signature is always twice the length of a point
  279. coordinate (e.g. 64 bytes for P-256).
  280. - ``'der'``, the signature is a ASN.1 DER SEQUENCE
  281. with two INTEGERs (``r`` and ``s``). It is defined in RFC3279_.
  282. The size of the signature is variable.
  283. randfunc (callable):
  284. A function that returns random ``bytes``, of a given length.
  285. If omitted, the internal RNG is used.
  286. Only applicable for the *'fips-186-3'* mode.
  287. .. _FIPS 186-3: http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
  288. .. _FIPS 186-4: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
  289. .. _NIST SP 800 Part 1 Rev 4: http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r4.pdf
  290. .. _RFC6979: http://tools.ietf.org/html/rfc6979
  291. .. _RFC3279: https://tools.ietf.org/html/rfc3279#section-2.2.2
  292. """
  293. # The goal of the 'mode' parameter is to avoid to
  294. # have the current version of the standard as default.
  295. #
  296. # Over time, such version will be superseded by (for instance)
  297. # FIPS 186-4 and it will be odd to have -3 as default.
  298. if encoding not in ('binary', 'der'):
  299. raise ValueError("Unknown encoding '%s'" % encoding)
  300. if isinstance(key, EccKey):
  301. order = key._curve.order
  302. private_key_attr = 'd'
  303. if key._curve.name == "ed25519":
  304. raise ValueError("ECC key is not on a NIST P curve")
  305. elif isinstance(key, DsaKey):
  306. order = Integer(key.q)
  307. private_key_attr = 'x'
  308. else:
  309. raise ValueError("Unsupported key type " + str(type(key)))
  310. if key.has_private():
  311. private_key = getattr(key, private_key_attr)
  312. else:
  313. private_key = None
  314. if mode == 'deterministic-rfc6979':
  315. return DeterministicDsaSigScheme(key, encoding, order, private_key)
  316. elif mode == 'fips-186-3':
  317. if isinstance(key, EccKey):
  318. return FipsEcDsaSigScheme(key, encoding, order, randfunc)
  319. else:
  320. return FipsDsaSigScheme(key, encoding, order, randfunc)
  321. else:
  322. raise ValueError("Unknown DSS mode '%s'" % mode)