Category Archives: Security

OpenWrt, easy-rsa, openvpn and stunnel

Certificates are confusing. I have wanted to generate self signed certificates on OpenWrt using easy-rsa, and use them for openvpn and stunnel. Below are the relevant commands and configurations.

easy-rsa
The vpn guide for OpenWrt is quite good. A summary:

# cd /etc/easy-rsa
# vim vars                   -- edit as you like
# source ./vars
# build-ca                   -- generates ca.crt
# build-dh                   -- generates dh2048.pem
# build-key-server myserver  -- generates myserver.[crt+key+csr]
# build-key myclient         -- generates myclient.[crt+key+csr]

For stunnel purposes, you need to copy/rename your .crt file to .pem. The content is the same.

The .csr files are not needed. The clients need the ca.crt plus their .crt (or .pem) and .key files.

openvpn server

option ca '/etc/openvpn/ca.crt'
option cert '/etc/openvpn/myserver.crt'
option key '/etc/openvpn/myserver.key'
option dh '/etc/openvpn/dh2048.pem'

openvpn client

option ca '/etc/openvpn/ca.crt'
option cert '/etc/openvpn/myclient.crt'
option key '/etc/openvpn/myclient.key'

stunnel server

cert = /etc/stunnel/myserver.pem
key = /etc/stunnel/myserver.key
CAfile = /etc/stunnel/ca.crt
verify = 2

stunnel client

cert = /etc/stunnel/myclient.pem
key = /etc/stunnel/mysclient.key
CAfile = /etc/stunnel/ca.crt
verify = 2

It looks very simple now, but without a working configuration it is not so easy to find the error.

Simple Integer Factorization and RSA key sizes

I have been playing with RSA lately, you know the encryption protocol where you generate two primes, multiply them, give the product away to be used for encryption by others and keeping the primes for yourself since they are needed for decryption (that was very simplified).

I have read that the largest known number to ever have been factorized was 768 bits long. Such a number looks like this (in hex):

6d733229f36b1fe086f39b5ae05d0155e7658480fe7c987fe5da51734b6b8c02
a7b6b22e5da0afc0867d7315405bddd9062da121a3b0b2663397ae8a65085d53
927279c1c330247ff20c2f1bd4b4f95375a74beefac29c519a8193e2614ffc19

For encryption to be safe for the next decades, keys that are 2048 or 4096 bits long are used. Or even longer.

One feature of RSA is that the output of encryption is never smaller than the size of the key (well, again, very simplified). So, imagine you want to encrypt 4-digit pin codes, one-by-one, using RSA with 1024-bit key, each pin code would be several hundred bytes, instead of just a few characters. For almost obvious reasons, you can not make a stream cipher of RSA or some other smart mode of operation to work around this problem (please let me know if I am wrong). This makes me want to use RSA with a small enough key to be secure enough for my purposes.

My questions

  1. What key sizes are trivial to break?
  2. What sizes require some qualified effort?
  3. How hard is it really to factorize big integers?

I found a tool called Yafu. It appears to be rather competent. It would require years of effort and advanced skills in math to write a better tool. For integers 320 bits and larger, Yafu requires GGNFS – a seriously very complicated piece of software that also hard to compile. Luckily there are nice windows binaries from Jeff Gilchrist. I also downloaded a binary version of Yafu for Windows. The examples below use Cygwin to have access to some Unix tools (bc, tr, openssl).

Generating a Prime product and factorizing it
There is a very nice JavaScript project for RSA. Set the bit size to whatever you want (I use 128 in this example), click generate, and obtain “Modulus”:

Modulus (hex): 81653c1536c42501a815431dac804899

Convert to upper case using tr:

$ echo 81653c1536c42501a815431dac804899 | tr '[:lower:]' '[:upper:]'
81653C1536C42501A815431DAC804899

Then use bc to convert to decimal:

$ bc -q
ibase=16
81653C1536C42501A815431DAC804899
171996052064283111843964589052488861849
quit

Finally, factorize using yafu:

$ echo "factor(171996052064283111843964589052488861849)" | ./yafu-x64.exe


06/14/14 13:24:28 v1.34.5 @ TOR, System/Build Info:
Using GMP-ECM 6.3, Powered by GMP 5.1.1
detected         Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz
detected L1 = 32768 bytes, L2 = 6291456 bytes, CL = 64 bytes
measured cpu frequency ~= 3108.870930
using 20 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>>
fac: factoring 171996052064283111843964589052488861849
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C39
rho: x^2 + 2, starting 1000 iterations on C39
rho: x^2 + 1, starting 1000 iterations on C39
pm1: starting B1 = 150K, B2 = gmp-ecm default on C39
ecm: 30/30 curves on C39, B1=2K, B2=gmp-ecm default

starting SIQS on c39: 171996052064283111843964589052488861849

==== sieving in progress (1 thread):     624 relations needed ====
====           Press ctrl-c to abort and save state           ====
546 rels found: 293 full + 253 from 2026 partial, (41408.50 rels/sec)

SIQS elapsed time = 0.0740 seconds.
Total factoring time = 0.2690 seconds


***factors found***

P20 = 14624642445740394983
P20 = 11760701343804754303

ans = 1

Now I wrote a little bash script that does everything:

#!/bin/bash

INTSIZE=$1

rm -f key.*
rm -f *.log
rm siqs.dat

BC_LINE_LENGTH=9999
export BC_LINE_LENGTH

openssl genrsa -out key.pem $INTSIZE
openssl rsa -in key.pem -noout -modulus | cut -f 2 -d '=' > key.hex
echo "ibase=16 ; $( cat key.hex )" | bc > key.dec
echo "factor($( cat key.dec ))" | ./yafu-x64.exe -threads 4

I am using yafu with default settings – very hard to imagine I can do anything better than the yafu author. For 320 bits and above, the GGNFS library is required. Performance for different sizes of integers to factorize (using the QuadCore Intel i5-2400 from the output above):

Bits Time Notes
128 0.28s
160 0.33s
192 1.86s
224 8.02s
256 52.6s
288 265s
320 3649s ~30Mb Temp files
352 9291s
384 27261s ~660Mb Temp files
512 73 days http://lukenotricks.blogspot.se/2009/08/solo-desktop-factorization-of-rsa-512.html

Well, this means that a normal Windows desktop computer can break 512 bit RSA within days or weeks. Below 512 bits, brute force is not much of a challenge, and using 256-bit RSA for encrypting short messages is (unfortunately, since it was what I ultimately wanted to explore) just ridiculous.

As keys get larger, more temp disk space is required, somewhere between 512-768 bits it gets seriously complex (I claim this, as a 768 bit integer is the largest to have been known to ever been factorized into two primes). You can read about General Number Field Sieves to get some background.

Not everyone is capable of extracting the Modulus integer from en encrypted file or network stream, installing Yafu, waiting for a little while and then use the two obtained primes to actually generate a fake certificate or actually decrypt anything. So, if you want to encrypt data to prevent your boss or your wife from reading it, you can probably use any key size you like – or why not use an encrypted zip file or an encrypted MS Word file?

If you have a skilled and motivated enemy, who are willing to put some effort into breaking your encryption, I would not use anything close to 512 bits. I assume the police, or FRA (in Sweden) or NSA can break 512 bit RSA within hours or faster when they need to.

I am not giving any sources for any of my claims here. I am not an expert in factorizing large-prime-products, and I am certainly not an expert in Quantum Computers. But as I understand it; 1024 bits should be fine, but perhaps in 10-20 years using even larger keys may make sense, and I don’t expect to see Quantum computers practically breaking real RSA keys in the next 50 years.

It is fascinating that a 128-bit AES key is completely beyond hope to brute force for any power on earth, while 128-bit RSA keys are worthless.

I now wonder, are there other asymmetric ciphers that are secure with significantly shorter keys than RSA?

This site defaced

This site was defaced on Saturday, January 5. WordPress was up to date. Perhaps during the next few days I can find out how the attack happened. Nobody really wanted to destroy anything and now I am back online – let’s see for how long.

The skilled hackers were Egyptian Shell Team. They want freedom and independence for Palestine and seek the destruction of Israel. So it was quite logical and brave of them to deface my site. In the end, it is all about being part of the problem, or being part of the solution, right?

Take care!

Simple Encryption Library for QT (improved)

A while ago I posted a simple encryption library for QT on this blog. I have now made some improvements and publish a new version. Major improvements are:

  1. Improved performance
  2. Added non patented Serpent Algorithm
    (easy to include and build without RC5)

As before, SimpleQtCryptor should work on all QT platforms without modification. It has no dependencies to anything outside QT and just uses qt datatypes.

Performance – SimpleQtCryptor vs OpenSSL
Since encryption is just overhead to any program using it performance is important. I have tried to optimize SimpleQtCryptor as much as possible, without making the code hard to read or risking portability.

For practical purposes, its performance is comparable to that of OpenSSL. This is on an Athlon II X2 250 3GHz cpu running Ubuntu:

                                                                OPENSSL
RC5-32/CBC      RC5-64/CBC      RC5-64/CFB      Serpent/CFB     AES-128-CFB
-----------------------------------------------------------------------------
6.5s / 9.0s     3.5s / 6.1s     3.2s / 5.9s     16.4s / 17.6s   5.8s / 7.8s
6.3s / 9.5s     3.5s / 6.1s     3.1s / 5.7s     16.4s / 19.0s   6.0s / 8.3s
-----------------------------------------------------------------------------

Values are presented as user time/real time (including a sync command).
First line is encrypt, second line is decrypt. The data is a 512MB file.

The first 4 columns are SimpleQtCryptor using different algorithms and modes of operation. The last column is 128-bit AES for OpenSSL.

Performance – different machines
For different machines, benchmarks have been made (just algorithm, no streaming or I/O):

                                RC5-32  RC5-64  Serpent 
------------------------+-------------------------------
Athlon II X2 250 3GHz   | enc   4.6s    2.3s    14.6s   
512Mb data, Ubuntu      | dec   4.6s    2.3s    14.8s
------------------------+-------------------------------
Athlon II X2 250 3GHz   | enc   5.8s    3.2s    22.4s
512Mb data, Windows7 64 | dec   5.6s    3.2s    20.6s
------------------------+-------------------------------
Intel Core i5 2.3GHz    | enc   6.9s    3.4s    19.1s
512Mb data, Mac OS X    | dec   6.6s    3.3s    19.2s
------------------------+-------------------------------
Intel Pentium(M) 2.0Ghz | enc   10.9s   47s     35s
512Mb data, Windows7 32 | dec    9.8s   46s     36s
------------------------+-------------------------------
Intel Atom z520 1.33Ghz | enc   20.2s   83s     113s
512Mb data, Windows7 32 | dec   19.2s   84s     130s
------------------------+-------------------------------
PPC G4 866Mhz           | enc   20.4s   62s     85s
512Mb data, Mac OS X    | dec   32.9s   61s     83s
------------------------+-------------------------------
ARM,QNAP TS109 500Mhz   | enc   8.6s    30.4s   58.4s   
64Mb data, Debian       | dec   8.2s    26.4s   92.7s   
------------------------+-------------------------------

It is fascinating to see how different CPUs perform. A few comments:

  • 32 bit machines suffer more from the 64 bit version of RC5, than the other way around – stay with 32 bit unless you know most clients will be 64 bit
  • Serpent uses a precomputed SBOX table (16kb), and CPUs with little cache (Atom and especially the ARM) underperforms on Serpent
  • The Mac OS X G4 compiler fails to use the assembler right roll used in decryption (but finds left roll for encryption) which makes RC5-32 suffer (but not Serpent, for some reason).
  • See how much slower the program runs on Windows 7 than on Ubuntu (on the Athlon II X2). The Microsoft SDK and Microsoft compiler is used, and I expected it to outperform gcc, not the other way around. I wonder if this applies to 32-bit machines as well, but currently I have no dual boot 32 bit machine available.

Building
As usual, building is easy with QT:

 $ qmake
 $ make

Including in your project
If you want to include the SimpleQtCryptor in your project just copy these three files to your project:

  simpleqtcryptor.h
  simpleqtcryptor.cpp
  serpent_sbox.h (not necessary, but improves serpent performance 5-10 times)

You only need to #include simpleqtcryptor.h.

In the beginning of simpleqtcryptor.h there is a #define WITHRC5 that you can remove if you do not want RC5 in your program (for legal reasons).

The README file should tell you most things you need to know to include and use the library.

Disclaimer
Bad implementations of encryption algorithms is a very bad idea. I believe my implementation is correct and secure – I can not guarantee it. Implementation details (especially regarding modes of operations) make this library incompatible with other encryption libraries. You can not (expect to) decrypt data with any other implementation, even if they use the same encryption algorithms.

License
The source code for SimpleQtCryptor is here released under the GPLv3 license. If you need another license for the (not patent encumbered) Serpent part I will try to be flexible.

Background
The implementation of Serpent was originally coded in 2000, before the AES competition was resolved. Later Serpent lost to Rijndael, which became AES. In 2011 this Serpent implementation was ported to QT and optimized.

The implementation of RC5 was made in 2010 because I wanted simple encryption for QT, without being dependent on any non-qt-components. RC5 was chosen (despite it is patent protected) because it is a very simple algorithm to implement.

The command line tool
The library comes with a command line tool. The purposes of the command line tool is:

  • To demonstrate how to use the library in QT code
  • To facilitate self-test functionality – you can run this after building on your machine/OS/qt version to ensure compability with other builds.
  • To be used as a benchmark tool

If you want a simple command line encryption tool I strongly recommend you use OpenSSL instead!

This is how to use command line tool:

  SimpleQtCryptor -t testfile
  SimpleQtCryptor -b e|d rc532|rc564|spt Mb (benchmark Mb)
  SimpleQtCryptor -e OPTIONS
  SimpleQtCryptor -d OPTIONS
  SimpleQtCryptor -h
OPTIONS:
  -k SecretFile (preferred to -p)
  -p Secret (default = )
  -i IndataFile
  -o OutdataFile
  -rc5    : use native RC5 algorithm (default)
  -rc532  : use 32-bit RC5
  -rc564  : use 64-bit RC5
  -spt    : use Serpent algorithm
  -cbc    : CBC
  -cfb    : CFB (default)
  -n      : no header
  -v      : verbose

Download
Source code: SimpleQtCryptor-1.0.0.tgz
Command line tool for Windows: SimpleQtCryptor-1.0.0-x86.exe, SimpleQtCryptor-1.0.0-x64.exe

At this point I don’t supply any binaries for Linux or Mac OS X, however a Symbian version should show up some day.

Simple encryption library for QT (RC5)

Update:Also check out the new improved library.

A while ago I did some QT programming. I think the QT API is very good and useful. I like things about C++ more than Java, but at the same time QT takes away most of the annoyances with C++. Especially, developing cross-platform GUI applications is very nice with QT.

One thing I missed was a simple encryption library. I mean, there is QCA, but how simple is it to use?

So, I did the forbidden thing, and implemented my own encryption library. Ok – it is for many reasons a very stupid thing to do. But it was fun, I did it anyway, it works, and I will share it with you 😉

Well, I did another forbidden thing; I based my library on RC5 – a very elegant and simple encryption algorithm, protected by patents (at least in the US, where I do not live). Anyway, it is of course allowed to make an open source implementation of RC5.

The downloadable package contains three things: the library, a command line encryption utility using the library, and a little command line “unit test” tool. The files are named as:

  • main.cpp – test utility
  • simpleqtrc5.* – the library
  • simpleqtrc5_test.* – the unit test tool

As always with QT, building is very easy:

  $ qmake
  $ make

I used QT 4.5 and QT 4.6. Perhaps you are fine with older versions as well.

I suggest you have a look in the main.cpp-file, or simpleqtrc5.h for examples, instructions and documentation.

The library of course uses QT datatypes, so you can use it very naturally from any QT code. The core is implemented in somewhat optimized C code, that only uses QT datatypes, so it should be 100% portable. There are no non-QT dependencies.

I have implemented both a 32 bit version and a 64 bit version of the algorithm. Of course, both versions work on any CPU, and you chose algorithm at runtime. 32 bit algorithm is faster on 32 bit cpu, and 64 bit algorithm is faster on 64 bit cpu. Maybe this is the only 64-bit implementation of RC5?

Performance is reasonable, as you can see in this example (Ubuntu 11.04, x64):

$ time md5sum 100Mb.bin
28a8c7a11327880877f21c78b7222273  100Mb.bin

real	0m0.238s
user	0m0.220s
sys	0m0.010s

$ time openssl enc -e -aes-128-cbc -k p4ssw0rd -in 100Mb.bin -out 100Mb.aes.enc

real	0m0.580s
user	0m0.510s
sys	0m0.060s

$ time openssl enc -d -aes-128-cbc -k p4ssw0rd -in 100Mb.aes.enc -out 100Mb.aes.dec

real	0m0.619s
user	0m0.460s
sys	0m0.150s

$ md5sum 100Mb.aes.dec
28a8c7a11327880877f21c78b7222273  100Mb.aes.dec

$ time ./SimpleQtRC5 -e -p p4ssw0rd -i 100Mb.bin -o 100Mb.rc5.enc

real	0m1.678s
user	0m1.540s
sys	0m0.120s

$ time ./SimpleQtRC5 -d -p p4ssw0rd -i 100Mb.rc5.enc -o 100Mb.rc5.dec

real	0m2.064s
user	0m1.970s
sys	0m0.090s

$ md5sum 100Mb.rc5.dec 
28a8c7a11327880877f21c78b7222273  100Mb.rc5.dec

$ ls -l 100Mb.*
-rw-r--r-- 1 freke freke 104857600 2011-05-04 19:16 100Mb.aes.dec
-rw-r--r-- 1 freke freke 104857632 2011-05-04 19:15 100Mb.aes.enc
-rw-r--r-- 1 freke freke 104857600 2011-05-04 19:10 100Mb.bin
-rw-r--r-- 1 freke freke 104857600 2011-05-04 19:19 100Mb.rc5.dec
-rw-r--r-- 1 freke freke 104857634 2011-05-04 19:19 100Mb.rc5.enc

Above you can see:

  1. Calculating md5 sum of 100Mb-file
  2. Encrypting using openssl/aes-128 in 0.6s
  3. Decrypting using openssl/aes-128 in 0.6s
  4. Calculating md5sum to confirm that decryption recovered original file
  5. Encrypting using QT/RC5 in 1.7s
  6. Decrypting using QT/RC5 in 2.1s
  7. Calculating md5sum to confirm that decryption recovered original file
  8. Listing 100Mb files

The test program is quite simple to use:

$ ./SimpleQtRC5 
SimpleRC5 (v0.0)
USAGE:
  SimpleRC5 -t testfile
  SimpleRC5 -e OPTIONS
  SimpleRC5 -d OPTIONS
  SimpleRC5 -h
OPTIONS:
  -k SecretFile (preferred to -p)
  -p Secret (default = )
  -i IndataFile
  -o OutdataFile
  -w32    : use 32-bit words
  -w64    : use 64-bit words
  -w      : use native CPU words (default)
  -cbc    : CBC
  -cfb    : CFB (default)
  -n      : no header
  -v      : verbose

The only thing to explain is that without the header, the program can not itself figure out what options to use to decrypt (32/64 bit or cbc/cfb). The header does not reveal anything at all.

!! Please download the new and improved library !!

You can download the source: SimpleQtRC5-0.1.tgz.

If you have any questions, suggestions or complaints just let me know! I really believe the library is stable and secure, and simple to use! I might document it better if anyone cares about it.

Choosing a good password

Security, particularly on the internet, is about passwords. I once read a very good (although a bit long) paper on how to chose good passwords, but when I want that paper, I never find it. And when people ask me about it, I never have a link.

So, the paper is called Simple Formula for Strong Passwords Tutorial, and can be downloaded here.