SAGE & cryptology

From YobiWiki
Jump to navigation Jump to search

Discussions

Docs

TODO

  • check licensing of different packages and compare them to requirements for sage
  • analyse structure of integers and strings and see if the representation from sage is compatible with the one from python
  • analyse the format of objects used by different libraries and see if they are compatible
  • write a unified API for the different libraries
  • write wrapper for internal C library

Available

sage.crypto

Sage Reference Manual
Constructions in Sage

  • sage.crypto.all
  • sage.crypto.cipher
  • sage.crypto.classical
  • sage.crypto.classical_cipher
    • hillchipher
    • substitutioncipher
    • transpositioncipher
    • vigenerecipher
  • sage.crypto.cryptosystem
  • sage.crypto.lfsr
    • Module Level Functions
      • lfsr_autocorrelation(L, p, k)
      • lfsr_connection_polynomial(s)
      • lfsr_sequence(key, fill, n)
    • Examples:
sage: F = GF(2)
sage: o = F(0)
sage: l = F(1)
sage: key = [l,o,o,l]; fill = [l,l,o,l]; n = 20
sage: s = lfsr_sequence(key,fill,n)
sage: lfsr_autocorrelation(s,15,7)
4/15
sage: lfsr_autocorrelation(s,int(15),7)
4/15

sage: F = GF(2)
sage: F
Finite Field of size 2
sage: o = F(0); l = F(1)
sage: key = [l,o,o,l]; fill = [l,l,o,l]; n = 20
sage: s = lfsr_sequence(key,fill,n); s
[1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0]
sage: lfsr_connection_polynomial(s)
x^4 + x + 1
sage: berlekamp_massey(s)
x^4 + x^3 + 1
  • sage.crypto.stream_cipher [1]
    • Class: LFSRCipher
    • Class: ShrinkingGeneratorCipher
      • new(input): input = connection polynomial & initial state
      • decimating_cipher(self)
sage: FF = FiniteField(2)
sage: P.<x> = PolynomialRing(FF)
sage: LFSR = LFSRCryptosystem(FF)
sage: IS_1 = [ FF(a) for a in [0,1,0,1,0,0,0] ]
sage: e1 = LFSR((x^7 + x + 1,IS_1))
sage: IS_2 = [ FF(a) for a in [0,0,1,0,0,0,1,0,1] ]
sage: e2 = LFSR((x^9 + x^3 + 1,IS_2))
sage: E = ShrinkingGeneratorCryptosystem()
sage: e = E((e1,e2))
sage: e.decimating_cipher()
(x^9 + x^3 + 1, [0, 0, 1, 0, 0, 0, 1, 0, 1])
      • keystream_cipher(self)
...
sage: e.keystream_cipher()
(x^7 + x + 1, [0, 1, 0, 1, 0, 0, 0])
  • sage.crypto.mq
    • SBox Class: sage.crypto.mq.SBOX: see wiki.sagemath.org
      • S.difference_distribution_matrix()
      • S.maximal_difference_probability()
      • S.interpolation_polynomial()
      • S.polynomials(degree=2)
    • Small Scale Variants of the AES (SR) Polynomial System Generator: cage.crypto.mq.sr Reference Manual
    • Multivariate Polynomial Systems: sage.crypto.mq.mpolynomialsystem [2]

PyCrypto, the Python Cryptography Toolkit

Sage ships PyCrypto (new maintainer's page?) which implements many standard cryptographic algorithms.
It is not really meant for research/education/playing around but for production code but maybe something could be done to have easier access to it from within Sage.
The docstring level documentation is horrible: 

sage: import Crypto.Cipher.IDEA
sage: Crypto.Cipher.IDEA?
   x.__init__(...) initializes x; see x.__class__.__doc__ for signature

Manual is available here.

INPUT/OUTPUT:

  • always "binary strings" where each character represents 8 bits


  • Hash functions(Manual): MD2, MD4, MD5, RIPEMD, SHA256, SHA
    • SHA1 example: on Sage Notebook
    • All hashing modules share the same interface. After importing a given hashing module, call the new() function to create a new hashing object. You can now feed arbitrary strings into the object with the update() method, and can ask for the hash value at any time by calling the digest() or hexdigest() methods. The new() function can also be passed an optional string parameter that will be immediately hashed into the object's state.[3]
      Using the argument digest_size you can get the digest size but its constant.
    • SHA is just SHA from the Python standard library (see crypto_src/Hash/SHA.py)
  • Block encryption algorithms(Manual): AES, ARC2, Blowfish, CAST, DES, Triple-DES, IDEA, RC5
    • AES & DES example: on Sage Notebook
    • Possibilities: Define a new cipher object after importing the module and define the key, mode (cbc,cfb,ecb or pgp) and possible IV.
      The object gives you two methods: 'encrypt()' and 'decrypt()'.
      For AES: S-Box not modifiable, LookUp Tables are being used.
  • Stream encryption algorithms: ARC4, simple XOR
  • Public-key algorithms(Manual): RSA, DSA, ElGamal, qNEW
    • Public key Modules
      construct(tuple)
      generate(size, randfunc, progress_func=None) => public key object
    • Public key Objects
      available methods: canencrypt(), cansign(), decrypt(tuple), encrypt(string, K), hasprivate(), publickey(), sign(string, K), size(), verify(string, signature)
    • RSA Example: (pycrypt manual)
  >>> from Crypto.Hash import MD5
  >>> from Crypto.PublicKey import RSA
  >>> RSAkey=RSA.generate(384, randfunc) # This will take a while...
  >>> hash=MD5.new(plaintext).digest()
  >>> signature=RSAkey.sign(hash, "")
  >>> signature # Print what an RSA sig looks like--you don't really care.
  ('\021\317\313\336\264\315' ...,)
  >>> RSAkey.verify(hash, signature) # This sig will check out
  1
  >>> RSAkey.verify(hash[:-1], signature)# This sig will fail
  0
    • Second RSA example[4]:
from Crypto.PublicKey import RSA
from Crypto.Util.randpool import RandomPool
rpool = RandomPool()
privkeyA = RSA.generate(368, rpool.get_bytes)
privkeyB = RSA.generate(368, rpool.get_bytes)
pubkeyA = privkeyA.publickey()
pubkeyB = privkeyB.publickey()
msg = 'blah blah'
signed_msg = privkeyA.sign(msg, ) # Assumed the second parameter
encrypted_msg = pubkeyB.encrypt(msg, )
decrypted_msg = privkeyB.decrypt(encrypted_msg)
print pubkeyA.verify(decrypted_msg, signed_msg) # Should return true
print pubkeyB.verify(decrypted_msg, signed_msg) # Should return false
  • Protocols: All-or-nothing transforms, chaffing/winnowing
  • Miscellaneous: RFC1751 module for converting 128-key keys into a set of English words, primality testing
    • Crypto.Util.number
      GCD(x,y),getPrime(N, randfunc),getRandomNumber(N, randfunc),inverse(u, v),isPrime(N)
    • Crypto.Util.randpool
      The randpool module implements a strong random number generator in the RandomPool class. The internal state consists of a string of random data, which is returned as callers request it. The class keeps track of the number of bits of entropy left, and provides a function to add new random data; this data can be obtained in various ways, such as by using the variance in a user's keystroke timings.
  • Some demo programs (currently all quite old and outdated)


Bug:

from Crypto.PublicKey import RSA
from Crypto.Util import randpool
randfunc = randpool.RandomPool()
RSAkey = RSA.generate(384, randfunc.get_bytes)
Traceback (most recent call last): 

 File "<stdin>", line 1, in <module>
 File "/home/saged/.sage/sage_notebook/worksheets/tiftof/22/code/23.py", line 6, in <module>
   RSAkey = RSA.generate(Integer(384), randfunc.get_bytes)
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/sympy/plotting/", line 1, in <module>
   
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/Crypto/PublicKey/RSA.py", line 217, in generate_c
   p = pubkey.getPrime(bits/2, randfunc)
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/Crypto/Util/number.py", line 89, in getPrime
   number=getRandomNumber(N, randfunc) | 1
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/Crypto/Util/number.py", line 54, in getRandomNumber
   value |= 2L ** (N-1)                # Ensure high bit is set
 TypeError: unsupported operand type(s) for |=: 'long' and 'sage.rings.rational.Rational'

Happens only when running in Sage not in Python

Bug 2:

When using getrandbits instead of randfunc.get_bytes

from Crypto.PublicKey import RSA
from Crypto.Util import randpool
RSAkey = RSA.generate(384, getrandbits)

 Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
 File "/home/saged/.sage/sage_notebook/worksheets/tiftof/23/code/28.py", line 6, in <module>
   RSAkey = RSA.generate(Integer(384),getrandbits)
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/sympy/plotting/", line 1, in <module>
   
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/Crypto/PublicKey/RSA.py", line 217, in generate_c
   p = pubkey.getPrime(bits/2, randfunc)
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/Crypto/Util/number.py", line 89, in getPrime
   number=getRandomNumber(N, randfunc) | 1
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/Crypto/Util/number.py", line 53, in getRandomNumber
   value = bytes_to_long(S)
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/Crypto/Util/number.py", line 185, in bytes_to_long
   length = len(s)
 TypeError: object of type 'long' has no len()

OpenSSL

Manual (incomplete, for example: no AES documentation)
OpenSSL book on Google Books
Functionality in OpenSLL:

  • SYMMETRIC CIPHERS
blowfish(3), cast(3), des(3), idea(3), rc2(3), rc4(3), rc5(3)
Block Cipher Modes available: ECB, CBC, CFB, OFB
Padding: only PKCS7 padding available?
AES is same implementation as in pycrypto and only supports ECB and CBC (p. 175 in OpenSSL book)
  • PUBLIC KEY CRYPTOGRAPHY AND KEY AGREEMENT
dsa(3), dh(3), rsa(3)
  • CERTIFICATES
x509(3), x509v3(3)
  • AUTHENTICATION CODES, HASH FUNCTIONS
hmac(3), md2(3), md4(3), md5(3), mdc2(3), ripemd(3), sha(3)
CBC-MAC and XCBC-MAC algorithms for OpenSSL are provided here.
  • AUXILIARY FUNCTIONS
err(3), threads(3), rand(3), OPENSSL_VERSION_NUMBER(3)
  • INPUT/OUTPUT, DATA ENCODING
asn1(3), bio(3), evp(3), pem(3), pkcs7(3), pkcs12(3)
  • INTERNAL FUNCTIONS
bn(3), buffer(3), lhash(3), objects(3), stack(3),txt_db(3)


Functionality of OpenSSL in Sage is provided via the PyOpenSSL wrapper. A more complete wrapper is M2Crypto but it is not available as a package for Sage. Still have to try to import it

PyOpenSSL

http://pyopenssl.sourceforge.net/pyOpenSSL.html/

  • X509 objects
  • 509Name objects
  • X509Req objects
    X509Store objects
  • PKey objects
  • PKCS7 objects
  • PKCS12 objects
  • X509Extension objects
  • NetscapeSPKI objects


Looks like less functionality than PyCrypto => PyCrypto seems like a better candidate to adjust, else we would have to extend the PyOpenSSL wrapper AND OpenSSL itself for any wanted extended functionality.

M2Crypto

Homepage
API documentation
Oreilly: OpenSSL p. 258-266
INPUT/OUTPUT:

  • always "binary strings" where each character represents 8 bits


  • symmetric ciphers (in EVP module)
    • AES example: on Sage Notebook
    • RC4 example: on Sage Notebook
    • EVP module (from M2Crypto import EVP)= message digests, symmetric ciphers and PK algo's
    • A Cipher and Message Digest example:
      see here
  • message digests (MD5, SHA1, RipeMD-160) (in EVP module)
  • HMAC
    • example: on Sage Notebook
    • 2 possibilities: using the HMAC class or the hmac() function
  • RSA, DSA, DH (in EVP module)
  • SSL functionality to implement clients and servers.
  • HTTPS extensions to Python's httplib, urllib, and xmlrpclib.
  • Unforgeable HMAC'ing AuthCookies for web session management.
  • FTP/TLS client and server.
  • S/MIME.
  • ZServerSSL: A HTTPS server for Zope.
  • ZSmime: An S/MIME messenger for Zope.


More functionality than the PyOpenSSL wrapper, but not available as a Sage package. Worth importing if it provides extra functionality to PyCrypto.

Setup and import
sudo aptitude install openssl libssl-dev python-dev

$ python setup.py build
$ python setup.py install

sage: import sys                                        
sage: sys.path.append('/usr/lib/python2.5/site-packages')
sage: import M2Crypto

GnuTLS

Manual
Standard package in sage.
Mostly for certification and not for basic cryptography.

  • Support for TLS 1.1, TLS 1.0 and SSL 3.0 protocols
Since SSL 2.0 is insecure it is not supported.
TLS 1.2 is supported but disabled by default.
  • Support for TLS extensions: server name indication, max record size, opaque PRF input, etc.
  • Support for authentication using the SRP protocol.
  • Support for authentication using both X.509 certificates and OpenPGP keys.
  • Support for TLS Pre-Shared-Keys (PSK) extension.
  • Support for Inner Application (TLS/IA) extension.
  • Support for X.509 and OpenPGP certificate handling.
  • Support for X.509 Proxy Certificates (RFC 3820).
  • Supports all the strong encryption algorithms (including SHA-256/384/512), including Camellia (RFC 4132).
  • Supports compression.

Python-GnuTLS

http://pypi.python.org/pypi/python-gnutls/1.1.5
API reference built on local machine.
Same story as with OpenSSL: C-library + python wrapper

TLS Lite

Homepage
Mailing List Archive
TLS Lite hasn't been updated since February 21, 2005

INPUT/OUTPUT:

  • always "binary strings" where each character represents 8 bits


Not available as Sage package, but it is pure python

"TLS Lite is a free python library that implements SSL 3.0, TLS 1.0, and TLS 1.1. TLS Lite supports non-traditional authentication methods such as SRP, shared keys, and cryptoIDs in addition to X.509 certificates. TLS Lite is pure Python, however it can access OpenSSL, cryptlib, pycrypto, and GMPY for faster crypto operations. TLS Lite integrates with httplib, xmlrpclib, poplib, imaplib, smtplib, SocketServer, asyncore, and Twisted."
Pure python implementations for:

  • AES:
    • example: on Sage Notebook
    • Interesting are AES.py, Python_AES.py and rijndael.py
      • rijndael.py originally here and was ported from this java code
      • Might be possible to modify SBox but only CBC-mode available (see Python_AES.py)
  • RC4
  • RSA
    • example: on Sage Notebook
    • signature = PKCS1-SHA1
    • input/output is array of bytes instead of binary string
      Use tlslite.utils.keyfactory.stringToBytes and tlslite.utils.keyfactory.bytesToString to convert between array of bytes and binary string
  • TripleDES
    • no pure python implementation. API available for cryptlib, openssl(m2crypto) and pycrypto
  • HMAC
  • tlslite.utils.cryptomath. ... interesting?
    base64ToBytes base64ToNumber base64ToString bytesToBase64 bytesToNumber gcd getBase64Nonce getRandomBytes getRandomNumber getRandomPrime getRandomSafePrime hashAndBase64 invMod isPrime lcm makeSieve mpiToNumber numberToBase64 numberToBytes numberToMPI numberToString numBytes powMod stringToBase64 stringToNumbe

Bug:
in tlslite/utils/compat.py line 73
Problem: when running sage: rsa = tlslite.utils.keyfactory.generateRSAKey(128,["python"]) 

Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
 File "/home/saged/.sage/sage_notebook/worksheets/tiftof/17/code/2.py", line 6, in <module>
   rsa = tlslite.utils.keyfactory.generateRSAKey(Integer(128),["python"])
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/sympy/plotting/", line 1, in <module>
   
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/tlslite/utils/keyfactory.py", line 35, in generateRSAKey
   return Python_RSAKey.generate(bits)
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/tlslite/utils/Python_RSAKey.py", line 98, in generate
   p = getRandomPrime(bits/2, False)
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/tlslite/utils/cryptomath.py", line 364, in getRandomPrime
   p = getRandomNumber(low, high)
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/tlslite/utils/cryptomath.py", line 213, in getRandomNumber
   howManyBits = numBits(high)
 File "/opt/sage-3.0.3/local/lib/python2.5/site-packages/tlslite/utils/compat.py", line 73, in numBits
   s = "%x" % n
TypeError: int argument required

Solution:
change s = "%x" % n to s = "%x" % int(n)
Remarks:
Problem in only present when working in sage not when using sage-python => sage is sending a non-int type to numBits() while python is always sending int's.
numBits() takes an input n and calculates how many bits it consists of by converting it to hex representation and then calculates the amount of bits by the total hexadecimal characters needed and the value of the last hex character.

Importing in Sage

sage: import sys                                        
sage: sys.path.append('/usr/lib/python2.5/site-packages')
sage: import tlslite
sage: from tlslite.api import *

Python

  • binascii module: conversion between "binary string" and "hexadecimal string"
    • convert hexadecimal to appropriate string input via:
      sage: import binascii
      sage: binascii.unhexlify("A0B1C2")
    • convert string output to hexadecimal via:
      sage: import binascii
      sage: binascii.hexlify("\xA0\xB1\xC2")
  • modules: hmac, md5, sha, hashlib[5] (contains: md5(), sha1(), sha224(), sha256(), sha384(), and sha512())

Misc

  • book written on Cryptography by David Kohel, using SAGE
  • pyDes: python implementation of DES and 3DES
  • Cryptool: open source windows program for educational use of cryptography
  • RSA implementation in Python
  • PyRijndael
    • based on Phil Fresle's VB implementation [6] (doesn't provide more comments)
    • two high level functions:
      • EncryptData(key, data): Encrypts data using key and returns encrypted string. Uses 256 bit Rijndael cipher. Key is built from first 32 characters of password. A 32-bit message length is attached to beginning of ciphertext.
      • DecryptData(key, data)
    • example in the code:
   PlainText="Hello World" *50
   Key="Secret"
   CipherText=EncryptData(Key,PlainText)
   PlainText2=DecryptData(Key,CipherText)
   print "PT :",PlainText
   print "KY :",Key
   print "PT2:",PlainText2
  • Collection of Python Crypto stuff: here
    • PBKDF2 pure python implementation + example: here
    • Public Key algo's in pure python: here
  • in Python:

Wishes

  • General trac
  • sage.crypto: block ciphers
  • Someone needs to replace FiniteField_ext_pari with the two NTL implementations (they are much faster).
  • elliptic and hyperelliptic curves over finite fields support is rather poor
  • algebraic aspects received some attention for the cryptanalysis of symmetric cryptographic algorithms, i.e. the cryptanalyst expresses the cipher as a large set of multivariate polynomials and attempts to solve the system. The most common case over GF(2) is handled by PolyBoRi. This library is the backbone of BooleanPolynomialRing and friends. This class needs testing, documentation, extension and bugfixes. Basically someone should sit down and add all the methods of MPolynomial[Ring]_libsingular to BooleanPolynomial[Ring] which make sense, add a ton of doctests and test the hell out of the library to make sure no SIGSEGVs surprise the user.
  • the module sage.crypto.mq is also relevant for the above.
  • Univariate polynomials over GF(2) are still implemented via NTL's ZZ_pX class rather than GF2X. This should be changed. Also this ticket has a link to gf2x a very small drop in replacement C library which claimed to be 5x faster than NTL. Though, a formal vote is needed to get it into Sage.
  • At the end of the day everything boils down to linear algebra. So if you improve that, everybody wins. Sparse linear algebra mod p is still too slow (Ralf-Phillip Weinmann did some work here wrapping code from eclib), there isn o special implementation for sparse linear algebra over GF(2) (both blackbox and e.g. reduced echelon forms), dense LA over GF(2) needs Strassen multiplication/reduction, dense LA over GF(2^n) should probably get implemented.

The ideal toolbox

This is a lengthy list but it's our Xmas list ;-) We aim to have a toolbox for research/education/playing not production optimizations required. So easy access, reconfigurability and clearness are more important!

Block ciphers

Block cipher algorithms

Make sure the internals are accessible and reconfigurable, particularly the S-BOXes.
Try to make generic constructors such as Feistel cipher, etc

  • Serpent
  • Twofish
  • Idea
  • DES, 3DES 112, 168
  • AES 128, 196, 256
  • Present

Modes of operation

Make sure we can select independently the block cipher encryption/decryption mode and the chaining "encryption/decryption" mode

  • Authentication modes
    • CMAC
    • XCBC
    • CBC-MAC
  • Authentication+encryption modes
    • CCM
    • GCM
  • Encryption modes
    • ECB
    • CBC
    • CTR
  • Disk encryption modes
    • LRW
    • XTS

Non-keyed hashes

  • MDC-2 (ISO 10118-2)

Paddings

  • Bit padding (can be done at bit level, others are at byte level)
DD DD DD 80 00 00 00 00
  • zeros
DD DD DD 00 00 00 00 00
  • PKCS7
DD DD DD 05 05 05 05 05
  • ISO 10126
DD DD DD 42 DB 8A 98 05
  • ANSI X.923
DD DD DD 00 00 00 00 05

Stream ciphers

Same thing, get the internals accessible and patchable

  • RC4
  • A5/1 A5/2
  • SNOW2 SNOW3G
  • SW candidates of eSTREAM:
    • HC-128
    • RABBIT
    • Salsa 20/12
    • SOSEMANUK
  • HW candidates of eSTREAM:
    • F-FCSR
    • Grain
    • MICKEY
    • Trivium
  • LFSR
  • Shrinking generator
  • Self-shrinking generator

One-way functions

  • MD5
  • SHA family
  • Whirlpool
  • RipeMD
  • MDC-2
  • RadioGatún

Ways to transform a block cipher into a hash

  • Davies-Meyer
  • Matyas-Meyer-Oseas
  • Miyaguchi-Preneel

MACs based on hash functions

  • HMAC
  • NMAC

Key derivation functions

  • KDF family
  • PBKDF2

Public-key cryptography

ECC

Others

  • RSA (encryption, signature, PKCS#1 v1.5 and v2.1, with and without CTR)
  • DSA
  • ElGamal
  • DH
  • XTR
  • Paillier
  • NTRUE

Pseudo-random generators

  • cf NIST
  • Mersenne Twister

Cryptanalysis tools

  • boolean functions & S-Box
    • algebraic degree
    • algebraic immunity
    • algebraic normal form (ANF)
    • non linearity
    • resiliency
    • Walsh transforms
    • cross-correlation
  • ECC point counting
    • complex multiplication?
  • factorisation solver
  • discrete log solver
  • statistical tests (diehard, FIPS...)
  • Field operations: addition, multiplication, inverses (normal and polynomial basis)

Cross Reference Table: wishes &lt;-&gt; availability

Retrieved from "https://wiki.yobi.be/index.php?title=SAGE_%26_cryptology&oldid=4658"