RSA.cpp 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315
  1. /*
  2. * Copyright (c) 2020, Ali Mohammad Pur <ali.mpfard@gmail.com>
  3. * All rights reserved.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions are met:
  7. *
  8. * 1. Redistributions of source code must retain the above copyright notice, this
  9. * list of conditions and the following disclaimer.
  10. *
  11. * 2. Redistributions in binary form must reproduce the above copyright notice,
  12. * this list of conditions and the following disclaimer in the documentation
  13. * and/or other materials provided with the distribution.
  14. *
  15. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  16. * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18. * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  19. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  21. * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  22. * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  23. * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24. * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25. */
  26. #include <LibCrypto/ASN1/ASN1.h>
  27. #include <LibCrypto/ASN1/DER.h>
  28. #include <LibCrypto/ASN1/PEM.h>
  29. #include <LibCrypto/PK/RSA.h>
  30. namespace Crypto {
  31. namespace PK {
  32. RSA::KeyPairType RSA::parse_rsa_key(const ByteBuffer& in)
  33. {
  34. // we are going to assign to at least one of these
  35. KeyPairType keypair;
  36. // TODO: move ASN parsing logic out
  37. u64 t, x, y, z, tmp_oid[16];
  38. u8 tmp_buf[4096] { 0 };
  39. UnsignedBigInteger n, e, d;
  40. ASN1::List pubkey_hash_oid[2], pubkey[2];
  41. ASN1::set(pubkey_hash_oid[0], ASN1::Kind::ObjectIdentifier, tmp_oid, sizeof(tmp_oid) / sizeof(tmp_oid[0]));
  42. ASN1::set(pubkey_hash_oid[1], ASN1::Kind::Null, nullptr, 0);
  43. // DER is weird in that it stores pubkeys as bitstrings
  44. // we must first extract that crap
  45. ASN1::set(pubkey[0], ASN1::Kind::Sequence, &pubkey_hash_oid, 2);
  46. ASN1::set(pubkey[1], ASN1::Kind::Null, nullptr, 0);
  47. dbg() << "we were offered " << in.size() << " bytes of input";
  48. if (der_decode_sequence(in.data(), in.size(), pubkey, 2)) {
  49. // yay, now we have to reassemble the bitstring to a bytestring
  50. t = 0;
  51. y = 0;
  52. z = 0;
  53. x = 0;
  54. for (; x < pubkey[1].size; ++x) {
  55. y = (y << 1) | tmp_buf[x];
  56. if (++z == 8) {
  57. tmp_buf[t++] = (u8)y;
  58. y = 0;
  59. z = 0;
  60. }
  61. }
  62. // now the buffer is correct (Sequence { Integer, Integer })
  63. if (!der_decode_sequence_many<2>(tmp_buf, t,
  64. ASN1::Kind::Integer, 1, &n,
  65. ASN1::Kind::Integer, 1, &e)) {
  66. // something was fucked up
  67. dbg() << "bad pubkey: " << e << " in " << n;
  68. return keypair;
  69. }
  70. // correct public key
  71. keypair.public_key.set(n, e);
  72. return keypair;
  73. }
  74. // could be a private key
  75. if (!der_decode_sequence_many<1>(in.data(), in.size(),
  76. ASN1::Kind::Integer, 1, &n)) {
  77. // that's no key
  78. // that's a death star
  79. dbg() << "that's a death star";
  80. return keypair;
  81. }
  82. if (n == 0) {
  83. // it is a private key
  84. UnsignedBigInteger zero;
  85. if (!der_decode_sequence_many<4>(in.data(), in.size(),
  86. ASN1::Kind::Integer, 1, &zero,
  87. ASN1::Kind::Integer, 1, &n,
  88. ASN1::Kind::Integer, 1, &e,
  89. ASN1::Kind::Integer, 1, &d)) {
  90. dbg() << "bad privkey " << n << " " << e << " " << d;
  91. return keypair;
  92. }
  93. keypair.private_key.set(n, d, e);
  94. return keypair;
  95. }
  96. if (n == 1) {
  97. // multiprime key, we don't know how to deal with this
  98. dbg() << "Unsupported key type";
  99. return keypair;
  100. }
  101. // it's a broken public key
  102. keypair.public_key.set(n, 65537);
  103. return keypair;
  104. }
  105. void RSA::encrypt(const ByteBuffer& in, ByteBuffer& out)
  106. {
  107. #ifdef CRYPTO_DEBUG
  108. dbg() << "in size: " << in.size();
  109. #endif
  110. auto in_integer = UnsignedBigInteger::import_data(in.data(), in.size());
  111. if (!(in_integer < m_public_key.modulus())) {
  112. dbg() << "value too large for key";
  113. out.clear();
  114. return;
  115. }
  116. auto exp = NumberTheory::ModularPower(in_integer, m_public_key.public_exponent(), m_public_key.modulus());
  117. auto size = exp.export_data(out);
  118. // FIXME: We should probably not do this...
  119. if (size != out.size())
  120. out = out.slice(out.size() - size, size);
  121. }
  122. void RSA::decrypt(const ByteBuffer& in, ByteBuffer& out)
  123. {
  124. // FIXME: Actually use the private key properly
  125. auto in_integer = UnsignedBigInteger::import_data(in.data(), in.size());
  126. auto exp = NumberTheory::ModularPower(in_integer, m_private_key.private_exponent(), m_private_key.modulus());
  127. auto size = exp.export_data(out);
  128. auto align = m_private_key.length();
  129. auto aligned_size = (size + align - 1) / align * align;
  130. for (auto i = size; i < aligned_size; ++i)
  131. out[out.size() - i - 1] = 0; // zero the non-aligned values
  132. out = out.slice(out.size() - aligned_size, aligned_size);
  133. }
  134. void RSA::sign(const ByteBuffer& in, ByteBuffer& out)
  135. {
  136. auto in_integer = UnsignedBigInteger::import_data(in.data(), in.size());
  137. auto exp = NumberTheory::ModularPower(in_integer, m_private_key.private_exponent(), m_private_key.modulus());
  138. auto size = exp.export_data(out);
  139. out = out.slice(out.size() - size, size);
  140. }
  141. void RSA::verify(const ByteBuffer& in, ByteBuffer& out)
  142. {
  143. auto in_integer = UnsignedBigInteger::import_data(in.data(), in.size());
  144. auto exp = NumberTheory::ModularPower(in_integer, m_public_key.public_exponent(), m_public_key.modulus());
  145. auto size = exp.export_data(out);
  146. out = out.slice(out.size() - size, size);
  147. }
  148. void RSA::import_private_key(const ByteBuffer& buffer, bool pem)
  149. {
  150. // so gods help me, I hate DER
  151. auto decoded_buffer = pem ? decode_pem(buffer) : buffer;
  152. auto key = parse_rsa_key(decoded_buffer);
  153. if (!key.private_key.length()) {
  154. dbg() << "We expected to see a private key, but we found none";
  155. ASSERT_NOT_REACHED();
  156. }
  157. m_private_key = key.private_key;
  158. }
  159. void RSA::import_public_key(const ByteBuffer& buffer, bool pem)
  160. {
  161. // so gods help me, I hate DER
  162. auto decoded_buffer = pem ? decode_pem(buffer) : buffer;
  163. auto key = parse_rsa_key(decoded_buffer);
  164. if (!key.public_key.length()) {
  165. dbg() << "We expected to see a public key, but we found none";
  166. ASSERT_NOT_REACHED();
  167. }
  168. m_public_key = key.public_key;
  169. }
  170. template<typename HashFunction>
  171. void RSA_EMSA_PSS<HashFunction>::sign(const ByteBuffer& in, ByteBuffer& out)
  172. {
  173. // -- encode via EMSA_PSS
  174. auto mod_bits = m_rsa.private_key().modulus().trimmed_length() * sizeof(u32) * 8;
  175. u8 EM[mod_bits];
  176. auto EM_buf = ByteBuffer::wrap(EM, mod_bits);
  177. m_emsa_pss.encode(in, EM_buf, mod_bits - 1);
  178. // -- sign via RSA
  179. m_rsa.sign(EM_buf, out);
  180. }
  181. template<typename HashFunction>
  182. VerificationConsistency RSA_EMSA_PSS<HashFunction>::verify(const ByteBuffer& in)
  183. {
  184. auto mod_bytes = m_rsa.public_key().modulus().trimmed_length() * sizeof(u32);
  185. if (in.size() != mod_bytes)
  186. return VerificationConsistency::Inconsistent;
  187. u8 EM[mod_bytes];
  188. auto EM_buf = ByteBuffer::wrap(EM, mod_bytes);
  189. // -- verify via RSA
  190. m_rsa.verify(in, EM_buf);
  191. // -- verify via EMSA_PSS
  192. return m_emsa_pss.verify(in, EM, mod_bytes * 8 - 1);
  193. }
  194. void RSA_PKCS1_EME::encrypt(const ByteBuffer& in, ByteBuffer& out)
  195. {
  196. auto mod_len = (m_public_key.modulus().trimmed_length() * sizeof(u32) * 8 + 7) / 8;
  197. #ifdef CRYPTO_DEBUG
  198. dbg() << "key size: " << mod_len;
  199. #endif
  200. if (in.size() > mod_len - 11) {
  201. dbg() << "message too long :(";
  202. out.trim(0);
  203. return;
  204. }
  205. if (out.size() < mod_len) {
  206. dbg() << "output buffer too small";
  207. return;
  208. }
  209. auto ps_length = mod_len - in.size() - 3;
  210. u8 ps[ps_length];
  211. arc4random_buf(ps, ps_length);
  212. // since arc4random can create zeros (shocking!)
  213. // we have to go through and un-zero the zeros
  214. for (size_t i = 0; i < ps_length; ++i)
  215. if (!ps[i])
  216. ps[i] = 0xfe;
  217. u8 paddings[] { 0x00, 0x02 };
  218. out.overwrite(0, paddings, 2);
  219. out.overwrite(2, ps, ps_length);
  220. out.overwrite(2 + ps_length, paddings, 1);
  221. out.overwrite(3 + ps_length, in.data(), in.size());
  222. out.trim(3 + ps_length + in.size()); // should be a single block
  223. #ifdef CRYPTO_DEBUG
  224. dbg() << "padded output size: " << 3 + ps_length + in.size() << " buffer size: " << out.size();
  225. #endif
  226. RSA::encrypt(out, out);
  227. }
  228. void RSA_PKCS1_EME::decrypt(const ByteBuffer& in, ByteBuffer& out)
  229. {
  230. auto mod_len = (m_public_key.modulus().trimmed_length() * sizeof(u32) * 8 + 7) / 8;
  231. if (in.size() != mod_len) {
  232. dbg() << "decryption error: wrong amount of data: " << in.size();
  233. out.trim(0);
  234. return;
  235. }
  236. RSA::decrypt(in, out);
  237. if (out.size() < RSA::output_size()) {
  238. dbg() << "decryption error: not enough data after decryption: " << out.size();
  239. out.trim(0);
  240. return;
  241. }
  242. if (out[0] != 0x00) {
  243. dbg() << "invalid padding byte 0 : " << out[0];
  244. return;
  245. }
  246. if (out[1] != 0x02) {
  247. dbg() << "invalid padding byte 1" << out[1];
  248. return;
  249. }
  250. size_t offset = 2;
  251. while (offset < out.size() && out[offset])
  252. ++offset;
  253. if (offset == out.size()) {
  254. dbg() << "garbage data, no zero to split padding";
  255. return;
  256. }
  257. ++offset;
  258. if (offset - 3 < 8) {
  259. dbg() << "PS too small";
  260. return;
  261. }
  262. out = out.slice(offset, out.size() - offset);
  263. }
  264. void RSA_PKCS1_EME::sign(const ByteBuffer&, ByteBuffer&)
  265. {
  266. dbg() << "FIXME: RSA_PKCS_EME::sign";
  267. }
  268. void RSA_PKCS1_EME::verify(const ByteBuffer&, ByteBuffer&)
  269. {
  270. dbg() << "FIXME: RSA_PKCS_EME::verify";
  271. }
  272. }
  273. }