Skip to content

Posts tagged ‘cryptography’

Recreating the enigma in python

May 19 11
by mat

Whilst on holiday I was challenged by a friend (mikemeat) to create an enigma in python. Here is what I wrote:

# -*- coding: utf-8 -*-  
from random import shuffle,randint,choice
from copy import copy
alphabet=range(0,26)

def shift(l, n): # Method to rotate arrays/cogs
	return l[n:] + l[:n]
	
class cog: # Simple substitution cipher for each cog
	def create(self):
		self.transformation=copy(alphabet)
		shuffle(self.transformation)
		return 
	def passthrough(self,i):
		return self.transformation[i]
	def passthroughrev(self,i):
		return self.transformation.index(i)
	def rotate(self):
		self.transformation=shift(self.transformation, 1)
	def setcog(self,a):
		self.transformation=a

class enigma: # Enigma class	
	def __init__(self, nocogs,printspecialchars):
		self.printspecialchars=printspecialchars
		self.nocogs=nocogs
		self.cogs=[]
		self.oCogs=[] # Create backup of original cog positions for reset
		
		for i in range(0,self.nocogs): # Create cogs
			self.cogs.append(cog())
			self.cogs[i].create()
			self.oCogs.append(self.cogs[i].transformation)
		
		# Create reflector
		refabet=copy(alphabet)
		self.reflector=copy(alphabet)
		while len(refabet)>0:
			a=choice(refabet)
			refabet.remove(a)
			b=choice(refabet)
			refabet.remove(b)
			self.reflector[a]=b
			self.reflector[b]=a

	def print_setup(self): # To print the enigma setup for debugging/replication
		print "Enigma Setup:\nCogs: ",self.nocogs,"\nCog arrangement:"
		for i in range(0,self.nocogs):
			print self.cogs[i].transformation
		print "Reflector arrangement:\n",self.reflector,"\n"
		
	def reset(self):
		for i in range(0,self.nocogs):
			self.cogs[i].setcog(self.oCogs[i])
			
	def encode(self,text):
		ln=0
		ciphertext=""
		for l in text.lower():
			num=ord(l)%97
			if (num>25 or num<0):
				if (self.printspecialchars): # readability
					ciphertext+=l 
				else:
					pass # security
			else:
				ln+=1
				for i in range(0,self.nocogs): # Move thru cogs forward...
					num=self.cogs[i].passthrough(num)
					
				num=self.reflector[num] # Pass thru reflector
				
				for i in range(0,self.nocogs): # Move back thru cogs...
					num=self.cogs[self.nocogs-i-1].passthroughrev(num)
				ciphertext+=""+chr(97+num) # add encrypted letter to ciphertext
				
				for i in range(0,self.nocogs): # Rotate cogs...
					if ( ln % ((i*6)+1) == 0 ): # in a ticker clock style
						self.cogs[i].rotate()
		return ciphertext

plaintext="""The most common arrangement used a ratchet and pawl mechanism. 
Each rotor had a ratchet with 26 teeth and, every time a key was pressed, each 
of the pawls corresponding to a particular rotor would move forward in unison, 
trying to engage with a ratchet, thus stepping the attached rotor once. A thin 
metal ring attached to each rotor upon which the pawl rode normally prevented 
this. As this ring rotated with its rotor, a notch machined into it would 
eventually align itself with the pawl, allowing it to drop into position, engage 
with the ratchet, and advance the rotor. The first rotor, having no previous 
rotor (and therefore no notched ring controlling a pawl), stepped with every 
key press. The five basic rotors (I–V) had one notch each, while the additional 
naval rotors VI, VII and VIII had two notches. The position of the notch on each 
rotor was determined by the letter ring which could be adjusted in relation to 
the core containing the interconnections. The points on the rings at which they 
caused the next wheel to move were as follows"""

x=enigma(4,True)
#x.print_setup()

print "Plaintext:\n"+plaintext+"\n"
ciphertext=x.encode(plaintext)
print "Ciphertext:\n"+ciphertext+"\n"

# To proove that encoding and decoding are symmetrical
# we reset the enigma to starting conditions and enter
# the ciphertext, and get out the plaintext
x.reset()
plaintext=x.encode(ciphertext)
print "Plaintext:\n"+plaintext+"\n"

Feel free to tear it apart and show me how much better/easier it could have been!

Bitcoins a cryptocurrency, free bitcoins and a rigged casino

Jul 14 10
by mat

Update: it’s currently quite difficult to get hold of bitcoins in the UK but localbitcoins works.



If your already aware of the awesomeness of public key cryptography (e.g. PGP or OTR), then you will probably appreciate Bitcoins.

You send coins by typing in someone’s address and how many coins to send and then your transaction will propagate around the p2p network. You receive coins in the same way by giving someone your address. In order to track transactions you can also make more addresses (and labels for them) which can also add to anonymity. Bitcoins are currently worth $0.0201 per bc (source)

Bitcoin program running

Bitcoin program running

Generating Bitcoins
You can opt to generate solutions to a specific crypotgraphic problem in exchange for bitcoins, by doing so your computer’s idle CPU will be used to solve this problem and when a solution is found you will be rewarded with some bitcoins, yay. There is also talk of speeding up the generation by using CUDA or similar tools here

5 Free Bitcoins
You can get 5 free bitcoins to start off your adventure into this new currency fromhere. This is a donation from somebody who wants to ensure that this currency is sucessful and as such this is a token of good faith and should not be exploited. You can also donate bitcoins to the fund to help this project.

Bitcoin casino (A Rigged Casino)
Now onto complain about a rigged casino that operates with bitcoins (Bitcasino).

Rigged and Broken roulette game on bitcoin casino

Rigged and Broken roulette game on bitcoin casino

I continually placed a bet (free play mode) on red, and for over 40 rounds it came up black, this has a probability of (20/7)^40 or 0.000000000708%. As unfair as this was then game then started getting worse constantly resulting in 0, however it would say “31 black odd” and in the side bar of past numbers “un” kept appearing which I guess means unknown.

I also tested a few of the slot machines to see if they were rigged too, and surely enough each rotation of the slots resulted in the exact same result every time, which was of course a losing one.

This bitcoin casino is rigged, buggy and not worth wasting your time with, it is much easier to lose money in other ways.

Conclusion
Bitcoin is an awesome idea and hopefully it will catch on and become sucessful, however be sure to avoid bitcasino! Also if anyone would like to donate some bitcoins then please send them to:
12Qxwa4d8s7bYHWVvNLkQZAVkJZrz8ReKB

Cracking real world salted MD5 passwords in python with several dictionaries

Jun 28 10
by mat

Recently a friend (who will remain unnamed for obvious reasons) asked me to penetration test a website he created. I found a very simple exploit where I could upload an avatar but the file was not checked to ensure it was an image, so I uploaded a php script I wrote an began exploring the server. I printed out all of the usernames, passwords and salts from the database to see how many of the 1,109 passwords could be easily cracked.

The passwords were stored as MD5 hashes with a random 6 character alphanumeric salt. To create the MD5 hash of the password the salt was prefixed to the password and then the combination was hashed. Thanks to this method we can employ a simple bruteforce/dictionary attack on the passwords. I will start with the wordlists creation, then results I obtained to keep your interest, and finally show my python code.

Creating wordlists
I already has two reasnoble sized dictionaries that I use for different things like wordcube. I used john the ripper on my double sized dictionary to create lots of common permutations on words, such as captial first letter, and a number affixed to the end. To do this you run john with the following parameters, where dic.txt is the input dictionary and dic_plus_rules.txt is the output from john with all of the additions it has made.

john –wordlist=dic.txt –rules –stdout > dic_plus_rules.txt

I also download two wordlists from openwall, one which is a list of ~3100 common passwords, and one labelled ALL that has a large amount of words (~4 million) in various languages. Because of the highly compressible nature of text the files are available in small gzip files. ALL is 11.5Mb which unzips to 41.4Mb and password 12kb which unzips to 21.8kb. There are also more wordlists avaliable for different languages, but the ALL file includes these.

The size of all of the wordlists I used is shown below:

Dictionary Combinations
English 42,987
Double-English 80,368
Double+john-rules 3,986,706
Openwall Common Passwords 3,158
Openwall ALL 3,917,116

Results

Dictionary Cracked Percentage Time
English 60 5.41% 80s
Double-English 65 5.86% 170s
Double+john-rules 116 10.46% 2.5hrs (8393s)
Openwall Common Passwords 112 10.10% 7s
Openwall All 210 18.94% 2.45hrs (8829s)
Total Passwords Obtained 254 22.90% ~5hrs

Comical passwords

Here are some of the more amusingly bad passwords, the number in brackets shows the frequency of the password.

Crap passwords: 123456 (18), password (4), 1234567 (4), 123456789 (3) 12345678 (2), 12345 (2), abc123 (2), asdfgh (2), nintendo (2), 123123, abcd1234, abcdefg, qwerty
Self-describing passwords: catholic, cowboy, creator, doger, ginger, killer, maggot, player, princess, skater, smallcock, smooth, super, superman, superstar, tester, veggie, winner, wolverine
Some other passwords:bananas, cheese, cinnamon, hampster ,DRAGON, dribble1, poopie, poopoo

Python Program

# -*- coding: utf-8 -*-
#pymd5cracker.py
import hashlib, sys
from time import time

# Change to commandline swtiches when you have the time!
hash = ""
hash_file = "hash2.csv"
wordlist = "mass_rules.txt"; 


# Read the hash file entered
try:
	hashdocument = open(hash_file,"r")
except IOError:
	print "Invalid file."
	raw_input()
	sys.exit()
else:
	# Read the csv values seperated by colons into an array
	hashes=[]
	for line in hashdocument:
		line=line.replace("\n","")
		inp = line.split(":")
		if (line.count(":")<2):
			inp.append("")
		hashes.append(inp)
	hashdocument.close();


# Read wordlist in
try:
	wordlistfile = open(wordlist,"r")
except IOError:
	print "Invalid file."
	raw_input()
	sys.exit()
else:
	pass

tested=0
cracked=0
tic = time()
for line in wordlistfile:
	
	line = line.replace("\n","")
	tested+=1
	for i in range(0,len(hashes)):
	
		m = hashlib.md5()
		m.update(hashes[i][2]+line)
		word_hash = m.hexdigest()
		if word_hash==hashes[i][1]:
			toc = time()
			cracked+=1
			hashes[i].append(line)
			print hashes[i][0]," : ", line, "\t(",time()-tic,"s)"

	# Show progress evey 1000 passwords tested
	if tested%1000==0:
		print "Cracked: ",cracked," (",tested,") ", line


# Save the output of this program so we can use again 
# with another program/dictionary adding the password 
# to each line we have solved.
crackout = open("pycrackout.txt","w")
for i in hashes:
	s=""
	for j in i:
		if s!="":
			s+=":"
		s+=j
	s+="\n"
	crackout.write(s)
crackout.close()

print "Passwords found: ",cracked,"/",len(hashes)
print "Wordlist Words :", test
print "Hashes computed: ",len(hashes)*tested
print "Total time taken: ",time()-tic,'s' 

Next

  • Play with more dictionaries
  • Speed up code:
    • Add multi-threading: My experience with multi-threading in python is that it doesn't work well for cpu intensive tasks, if you know otherwise please let me know.
    • Have a look at PyCUDA to see if I can use my graphics card to speed up the code significantly (another type of mutli-threading really...) without having to change language like in my previous post of CUDA MD5 cracking
  • Remove hash once found to stop pointless checking
  • Add command line switches to all it to be used like a real program

Cracking MD5 hashes (or passwords) ultra-fast with GPU acceleration

Jun 24 10
by mat

Do you want to crack MD5 hashes in at a rate of ~300MHash/s without a massive rainbow table? Do you have a CUDA enabled GFX card? If you said yes or maybe to these questions then read on for a brief introduction on how to compile and run a CUDA accelerated MD5 cracker (coded by Benjamin “Titan” Vernoux ).

Pre-Requisites and Downloading

Building in Ubuntu 10.04

Extract the archive and do a make on the source code. When doing this I came across two problems that can be fixed by modifying the common.mk file.

Problem 1: (cannot be declared weak)

$ make
/usr/include/string.h:43: error: inline function ‘void* memcpy(void*, const void*, size_t)’ cannot be declared weak
/usr/include/string.h:64: error: inline function ‘void* memset(void*, int, size_t)’ cannot be declared weak
/usr/include/bits/string3.h:49: error: inline function ‘void* memcpy(void*, const void*, size_t)’ cannot be declared weak
/usr/include/bits/string3.h:78: error: inline function ‘void* memset(void*, int, size_t)’ cannot be declared weak
/opt/cuda/bin/../include/common_functions.h:59: error: inline function ‘void* memset(void*, int, size_t)’ cannot be declared weak
/opt/cuda/bin/../include/common_functions.h:62: error: inline function ‘void* memcpy(void*, const void*, size_t)’ cannot be declared weak
/opt/cuda/bin/../include/math_functions.h:422: error: inline function ‘int __signbit(double)’ cannot be declared weak
/opt/cuda/bin/../include/math_functions.h:427: error: inline function ‘int __signbitf(float)’ cannot be declared weak
/opt/cuda/bin/../include/math_functions.h:440: error: inline function ‘int __signbitl(long double)’ cannot be declared weak
/usr/include/bits/mathcalls.h:350: error: inline function ‘int __signbit(double)’ cannot be declared weak
/usr/include/bits/mathcalls.h:350: error: inline function ‘int __signbitf(float)’ cannot be declared weak
/usr/include/bits/mathcalls.h:350: error: inline function ‘int __signbitl(long double)’ cannot be declared weak
/usr/include/bits/mathinline.h:36: error: inline function ‘int __signbitf(float)’ cannot be declared weak
/usr/include/bits/mathinline.h:42: error: inline function ‘int __signbit(double)’ cannot be declared weak
/usr/include/bits/mathinline.h:48: error: inline function ‘int __signbitl(long double)’ cannot be declared weak

Solution 1

# Debug/release configuration
ifeq ($(dbg),1)
COMMONFLAGS += -g
NVCCFLAGS += -D_DEBUG
BINSUBDIR := debug
LIBSUFFIX := D
else
##############Change the following line to have -O0 instead of -O2
COMMONFLAGS += -O0
BINSUBDIR := release
LIBSUFFIX :=
NVCCFLAGS += –compiler-options -fno-strict-aliasing
CXXFLAGS += -fno-strict-aliasing
CFLAGS += -fno-strict-aliasing
endif

Problem 2: (lcudart)

$ make
/usr/bin/ld: skipping incompatible /opt/cuda/lib/libcudart.so when searching for -lcudart
/usr/bin/ld: skipping incompatible /opt/cuda/lib/libcudart.so when searching for -lcudart
/usr/bin/ld: cannot find -lcudart
collect2: ld returned 1 exit status
make: *** [bin/linux/release/gpu_md5_crack_0.2.3] Error 1

Solution 2

############## Change lib to lib64 if using a 64 bit operating system
LIB := -L$(CUDA_INSTALL_PATH)/lib64 -L$(LIBDIR) -L$(COMMONDIR)/lib64/$(OSLOWER) -L$(NVIDIA_SDK_PATH)/lib

Remember that you should “make clean” in-between each attempt to compile.

Benchmarking

Once it has compiled nicely you can give it a testdrive with its build in benchmark (with an NVIDIA 260 GFX card). Just run with the -b option:

./gpu_md5_crack_0.2.3 -b
GPU_MD5_Crack v0.2.3 09 July 2009 LGPL for BackTrack 4.
Copyright (C) 2009 TitanMKD (titanmkd@gmail.com).

Benchmark Start
Using default CUDA GPU device:0
Cuda device ID:0, Device name:GeForce GTX 260, supporting CUDA:1.3,
multiProcessorCount:27, clockRate:1466.00 MHz, TotalMem:895.31 MB
******* Test 0 Start *******
Expected Password: 1234567890
MD5 Hash:e807f1fcf82d132f9bb018ca6738a19f, Start Password:1200000000, Total pwd to check:1000000000
Charset used 0:0123456789
MD5 brute force started

MD5 Cracked pwd=1234567890 hash=e807f1fcf82d132f9bb018ca6738a19f
Instant 200.02 Mhash/s(40.00 ms)
Average 190.49 Mhash/s, Total Time:0.21s(210.00 ms)
MD5 brute force finished
******* Test 0 End *******

******* Test 1 Start *******
Expected Password: azerty
MD5 Hash:ab4f63f9ac65152575886860dde480a1, Start Password:, Total pwd to check:1000000000
Charset used 1:abcdefghijklmnopqrstuvwxyz
MD5 brute force started

MD5 Cracked pwd=azerty hash=ab4f63f9ac65152575886860dde480a1
Instant 200.02 Mhash/s(40.00 ms)
Average 240.02 Mhash/s, Total Time:0.10s(100.00 ms)
MD5 brute force finished
******* Test 1 End *******

******* Test 2 Start *******
Expected Password: azer09
MD5 Hash:41b9cabe6033932eb3037fc933060adc, Start Password:, Total pwd to check:1000000000
Charset used 2:abcdefghijklmnopqrstuvwxyz0123456789
MD5 brute force started
Progress 5%, Pwd:6lmea, Instant 280.02 Mhash/s(28.57 ms)
MD5 Cracked pwd=azer09 hash=41b9cabe6033932eb3037fc933060adc
Instant 266.69 Mhash/s(30.00 ms)
Average 287.20 Mhash/s, Total Time:0.39s(390.00 ms)
MD5 brute force finished
******* Test 2 End *******

******* Test 3 Start *******
Expected Password: AZBVSD
MD5 Hash:fd049008572788d60140aaead79336cc, Start Password:, Total pwd to check:1000000000
Charset used 3:ABCDEFGHIJKLMNOPQRSTUVWXYZ
MD5 brute force started

MD5 Cracked pwd=AZBVSD hash=fd049008572788d60140aaead79336cc
Instant 266.69 Mhash/s(30.00 ms)
Average 240.02 Mhash/s, Total Time:0.10s(100.00 ms)
MD5 brute force finished
******* Test 3 End *******

******* Test 4 Start *******
Expected Password: AZ09AA
MD5 Hash:7a552dd9cdd49acc5320bad9c29c9722, Start Password:, Total pwd to check:1000000000
Charset used 4:ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
MD5 brute force started
Progress 5%, Pwd:6LMEA, Instant 266.69 Mhash/s(30.00 ms)
MD5 Cracked pwd=AZ09AA hash=7a552dd9cdd49acc5320bad9c29c9722
Instant 266.69 Mhash/s(30.00 ms)
Average 280.02 Mhash/s, Total Time:0.40s(400.00 ms)
MD5 brute force finished
******* Test 4 End *******

******* Test 5 Start *******
Expected Password: zaZAab
MD5 Hash:aef49f70bb7b923b8bc0a018f916ef64, Start Password:zCAAAA, Total pwd to check:1000000000
Charset used 5:ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
MD5 brute force started
Progress 17%, Pwd:zaDpoA, Instant 280.02 Mhash/s(28.57 ms)
MD5 Cracked pwd=zaZAab hash=aef49f70bb7b923b8bc0a018f916ef64
Instant 266.69 Mhash/s(30.00 ms)
Average 283.10 Mhash/s, Total Time:0.65s(650.00 ms)
MD5 brute force finished
******* Test 5 End *******

******* Test 6 Start *******
Expected Password: za0ZA9
MD5 Hash:062cc3b1302759722f48ac0b95b75803, Start Password:zaAAAA, Total pwd to check:1000000000
Charset used 6:ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789
MD5 brute force started

MD5 Cracked pwd=za0ZA9 hash=062cc3b1302759722f48ac0b95b75803
Instant 266.69 Mhash/s(30.00 ms)
Average 266.69 Mhash/s, Total Time:0.06s(60.00 ms)
MD5 brute force finished
******* Test 6 End *******

******* Test 7 Start *******
Expected Password: a^-*|
MD5 Hash:cf7dcf4c3eeb6255668393242fcce273, Start Password:a0000, Total pwd to check:1000000000
Charset used 7: !”#$%&’()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
MD5 brute force started

MD5 Cracked pwd=a^-*| hash=cf7dcf4c3eeb6255668393242fcce273
Instant 266.69 Mhash/s(30.00 ms)
Average 266.69 Mhash/s, Total Time:0.15s(150.00 ms)
MD5 brute force finished
******* Test 7 End *******

Benchmark End

So from the benchmark you can see that we are getting between 200 and 300 Mhash/s, that is about 250,000,000 hash attempts per second! AMAZING!!!

Number of combinations for different alphabets

Length 0-9 a-z a-z0-9 a-zA-Z a-zA-Z0-9
1 10 26 36 52 62
2 100 676 1,296 2,704 3,844
3 1,000 17,576 46,656 140,608 238,328
4 10,000 456,976 1,679,616 7,311,616 14,776,336
5 100,000 11,881,376 60,466,176 380,204,032 916,132,832
6 1,000,000 308,915,776 2,176,782,336 19,770,609,664 56,800,235,584
7 10,000,000 8,031,810,176 78,364,164,096 1,028,071,702,528 3,521,614,606,208
8 100,000,000 208,827,064,576 2,821,109,907,456 53,459,728,531,456 218,340,105,584,896
9 1,000,000,000 5,429,503,678,976 101,559,956,668,416 2,779,905,883,635,710 13,537,086,546,263,600
10 10,000,000,000 141,167,095,653,376 3,656,158,440,062,980 144,555,105,949,057,000 839,299,365,868,340,000

Estimated time (in seconds) to crack (at 250MHash/s)

Length 0-9 a-z a-z0-9 a-zA-Z a-zA-Z0-9
1 0.00 0.00 0.00 0.00 0.00
2 0.00 0.00 0.00 0.00 0.00
3 0.00 0.00 0.00 0.00 0.00
4 0.00 0.00 0.00 0.01 0.03
5 0.00 0.02 0.12 0.76 1.83
6 0.00 0.62 4.35 39.54 113.60
7 0.02 16.06 156.73 2,056.14 7,043.23
8 0.20 417.65 5,642.22 106,919.46 436,680.21
9 2.00 10,859.01 203,119.91 5,559,811.77 27,074,173.09
10 20.00 282,334.19 7,312,316.88 289,110,211.90 1,678,598,731.74

Full calculations avaliable here: MD5 hash cracking time using GPU accelerated brute forcing

What now?
Well you can crack MD5′s at an extremely accelerated rate, so enjoy doing so responsibly (let your morals guide you :P ). You could also explore the source code and make additions as you see fit, I am planning on modifying it to allow an extra parameter so that prefixes can be added if you already know how the password starts. This can be the case when someone has prefixed the password with a known salt.

How to create a cryptogram in python (random substitution cipher)

Apr 20 10
by mat

Cryptograms are enjoyable puzzles created from a saying or phrase encrypted with a substitutional cipher. They can be fun to decipher by hand by looking for common letter combinations, doublets, guesswork, and other flaws in this encryption mechanism.

I wrote a quick python script which will accept an input text and create a random substitutional cipher and encrypt it. It then outputs the cipher alphabet and the encrypted text.

Source code:

# -*- coding: utf-8 -*-
import sys
from random import randint
from string import maketrans

if (len(sys.argv)>1):
	# Normal alphabet 
	alphabet="abcdefghijklmnopqrstuvwxyz"

	# Randomly create a new cipherbet
	cipherbet=""
	left=alphabet
	for i in range(0,len(alphabet)):
		x=randint(0,len(left)-1)
		cipherbet+=left[x]
		left=left[:x]+left[x+1:]
	
	# Get input text to translate  
	text=sys.argv[1].lower()

	trantab = maketrans(alphabet,cipherbet)
	text=text.translate(trantab)

	# Replace unused letters in cipherbet with _'s  
	for i in cipherbet:
		if i not in text:
			cipherbet=cipherbet.replace(i,"_")

	# Print cipherbet (solution) and the text (cryptogram) 
	print cipherbet
	print text

Example usage

python create_cipher.py “The Science gets done. And you make a neat gun. For the people who are still alive.”
b_lpievrm_acqxuj_fzdgwn_o_
dri zlmixli vidz puxi. bxp oug qbai b xibd vgx. euf dri jiujci nru bfi zdmcc bcmwi.

Dell 1320c colour laser printer (Machine Identification Code microdots)

Apr 5 10
by mat

As you may or may not be aware some printers add extra information in order for the printer to be identified (primarily for counterfeiting case I believe). With colour laser printers this can be in the form of a small array of yellow dots printed onto you paper. Yellow dots are hardly visible to the naked eye, however if you are close enough and get the light at the right angle you can see them. If you have some blue leds or a blue light available this can make it much easier to see the dots (as the yellow dots will absorb the blue and look black).

CUPS test paper with non-visible yellow dots

CUPS test paper with non-visible yellow dots


CUPS test paper with non-visible yellow dots (closer)

CUPS test paper with non-visible yellow dots (closer)

Now much clearer under blue led illumination:

Yellow dots very clear under blue illumination on the dell 1320c colour laser printer

Yellow dots very clear under blue illumination on the dell 1320c colour laser printer


Yellow dots very clear under blue illumination (zoomed in)

Yellow dots very clear under blue illumination (zoomed in)

Unfortunately I my camera isn’t good enough quality and it doesn’t have a macro lens or feature so I can only show images at both extremes. Below are images captured with my microscope, you don’t have to look very far around the page, as the clusters are littered all over the page.

Microscope image of a few yellow dots on paper printed with dell 1320c

Microscope image of a few yellow dots on paper printed with dell 1320c


Microscope image of a two yellow dots (max zoom)

Microscope image of a two yellow dots (max zoom)

The Electronic frontier foundation have more information about the dots and have setup an address you can send a print test page to in order for them to build up a public defence case. Perhaps criminals will end up printing with yellow backgrounds to combat this method?

Python: Cryptography decoding a Caesar shift (frequency analysis)

Jan 4 10
by mat

Due to the simple nature of the Caesar cipher, it could easily be brute forced by trying all possible 25 keys and then looking by eye to see if the plaintext was revealed (this too can be automated by checking for common English words to see if the solution was probable). However the much more elegant method of frequency analysis can be used.

Below is a table of the frequency of letters in the English language:

Letter Frequency (percent) Frequency (decimal) Normalised Frequency
a 8.17% 0.08167 0.64297
b 1.49% 0.01492 0.11746
c 2.78% 0.02782 0.21902
d 4.25% 0.04253 0.33483
e 12.70% 0.12702 1.00000
f 2.23% 0.02228 0.17541
g 2.02% 0.02015 0.15864
h 6.09% 0.06094 0.47977
i 6.97% 0.06966 0.54842
j 0.15% 0.00153 0.01205
k 0.77% 0.00772 0.06078
l 4.03% 0.04025 0.31688
m 2.41% 0.02406 0.18942
n 6.75% 0.06749 0.53133
o 7.51% 0.07507 0.59101
p 1.93% 0.01929 0.15187
q 0.10% 0.00095 0.00748
r 5.99% 0.05987 0.47134
s 6.33% 0.06327 0.49811
t 9.06% 0.09056 0.71296
u 2.76% 0.02758 0.21713
v 0.98% 0.00978 0.07700
w 2.36% 0.02360 0.18580
x 0.15% 0.00150 0.01181
y 1.97% 0.01974 0.15541
z 0.07% 0.00074 0.00583

And shown graphically:

English Letter Frequency

English Letter Frequency

Using the following code we can use frequency analysis to find the solution to ciphertext created using the Caesar shift demonstrated previously (see Caesar shift and Caesar shift using makestrans).

from Numeric import *
from string import maketrans

def translator(text,alphabet,key):
	trantab = maketrans(alphabet,key)
	return text.translate(trantab)

def caesar_decode(ciphertext,s):
	alpha="abcdefghijklmnopqrstuvwxyz"
	return translator(ciphertext,alpha,alpha[-s:]+alpha[:-s])




class frequency_analysis:
	def __init__(self, ciphertext):
		self.cor=[0.64297,0.11746,0.21902,0.33483,1.00000,0.17541,
		0.15864,0.47977,0.54842,0.01205,0.06078,0.31688,0.18942,
		0.53133,0.59101,0.15187,0.00748,0.47134,0.49811,0.71296,
		0.21713,0.07700,0.18580,0.01181,0.15541,0.00583]
		self.ciphertext=ciphertext.lower()
		self.freq()
		self.min_error()
		self.key=self.minimum[0]
		self.solution=caesar_decode(self.ciphertext,self.minimum[0])

	def freq(self):
		self.arr=zeros(26,Float64)
		for l in self.ciphertext:
			x=ord(l)
			if (x>=97 and x<=122):
				self.arr[x-97]+=1.0
		self.arr/=max(self.arr)

	def error(self):
		e=0
		for i in range(0,len(self.arr)):
			e+=abs(self.arr[i]-self.cor[i])**2
		return e

	def min_error(self):
		self.minimum=[0,10000]
		for rot in range(0,25):
			e=self.error()
			print rot,e
			if e<self.minimum[1]:
				self.minimum[1]=e
				self.minimum[0]=rot
			x=self.arr[-1]
			del self.cor[-1]
			self.cor.insert(0,x)

ciphertext="ymjwj fwj ybt ydujx tk jshwduynts: tsj ymfy bnqq "+\
"uwjajsy dtzw xnxyjw kwtr wjfinsl dtzw infwd fsi tsj ymfy bnqq "+\
"uwjajsy dtzw ltajwsrjsy. ymnx nx f ajwd nrutwyfsy qjxxts yt "+\
"wjrjgjwjxujhnfqqd ktw fyyfhpx zxnsl kwjvzjshd fsfqdxnx bmnhm "+\
"wjvznwj qtsljw ufxxflj tk yjcy ns twijw yt fhmnjaj gjyyjw wjxzqyx."
FA=frequency_analysis(ciphertext)
print FA.solution

This code will calculate the error in statistical frequency for each letter squared to generate an error for each possible rotation. Using a sufficiently long piece of ciphertext this code should accurately reveal the Caesar rotation use. The table below shows the error for each rotation:

Rotation Error
0 4.11797847386
1 3.05305477067
2 3.70059678828
3 3.66330931218
4 3.5078619579
5 0.361318100755
6 3.17289666386
7 3.66072641654
8 3.39769855873
9 1.74854802027
10 2.92550921273
11 2.67524757297
12 2.86847189573
13 3.06980318397
14 2.56886153328
15 2.17180117031
16 2.24503724763
17 2.95579718798
18 1.74002183444
19 1.83328601011
20 1.74779021766
21 2.71332097813
22 1.5409364067
23 1.83209213494
24 1.54904808883

The lowest error is for 5 rotations (correctly so) with an error of 0.361318100755, the next lowest error is 22 rotations with an error of 1.5409364067. This is ~4.3x difference, which gives a very large degree of confidence to our solution and below is the deciphered text.

there are two types of encryption: one that will prevent your sister from reading your diary and one that will prevent your government. this is a very important lesson to remeberespecially for attacks using frequency analysis which require longer passage of text in order to achieve better results.

Future
The frequency analysis presented here can be used along with some other techniques in order to crack the viginere cipher.

Python: Cryptograph using maketrans for substitution and Caesar ciphers

Dec 22 09
by mat

I’ve rewritten the functions in my previous two posts (caesar and substitution ciphers) using the maketrans function from the strings module in python (With thanks to wumzi for pointing this out).

maketrans takes an input alphabet and an output alphabet and can then be used on a string. This can be used to greatly simplify the two ciphers I produced previously. Example below:

input_alphabet="abcde"
output_alphabet="12345"
trantab = maketrans(input_alphabet,output_alphabet)
text="translate abcdefg"
print text.translate(trantab)
# This will output:
# tr1nsl1t5 12345fg

This nows means my code can be rewritten in just a fraction of what it was before:

from random import shuffle
from string import maketrans

alphabet="abcdefghijklmnopqrstuvwxyz" + \
	 "1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ"+ \
         ":.;,?!@#$%&()+=-*/_<> []{}`~^"

def translator(text,alphabet,key):
	trantab = maketrans(alphabet,key)
	return text.translate(trantab)

def caesar_encode(plaintext,s,alphabet):
	return translator(plaintext,alphabet,alphabet[s:]+alphabet[:s])

def caesar_decode(ciphertext,s,alphabet):
	return translator(ciphertext,alphabet,alphabet[-s:]+alphabet[:-s])

def substitution_encode(plaintext,alphabet):
	randarray=range(0,len(alphabet))
	shuffle(randarray)
	key=""
	for i in range(0,len(alphabet)):
		key+=alphabet[randarray[i]]

	return translator(plaintext,alphabet,key),key

def substitution_decode(ciphertext,key,alphabet):
	return translator(ciphertext,key,alphabet)


# Example useage
plaintext="The wheels on the bus go round and round. round" + \
" and round. round and round. The wheels on the bus go round and"+ \
" round, all through the town!"


print 
print "SUBSTITUTION"
ciphertext,key=substitution_encode(plaintext,alphabet)
print "Key: ", key
print "Plaintext:", plaintext
print "Cipertext:", ciphertext
print "Decoded  :", substitution_decode(ciphertext,key,alphabet)

print 
print "CAESAR SHIFT"
ciphertext=caesar_encode(plaintext,5,alphabet)
print "Key: ", 5
print "Plaintext:", plaintext
print "Cipertext:", ciphertext
print "Decoded  :", caesar_decode(ciphertext,5,alphabet)

This will output the following

SUBSTITUTION
Key: &fywQ.%!lmx_sRGu:{<(5jqAXvMFgk]SIY[4iK+3P8pcV$2da@DT/ZnOJ*E>-r},BH16zUb#L?N`e7C ~9t)oW^=;h0
Plaintext: The wheels on the bus go round and round. round and round.round and round. The wheels on the bus go round and round, all through the town!
Cipertext: O!Q)q!QQ_<)GR)(!Q)f5<)%G){G5Rw)&Rw){G5Rw,){G5Rw)&Rw){G5Rw,{G5Rw)&Rw){G5Rw,)O!Q)q!QQ_<)GR)(!Q)f5<)%G){G5Rw)&Rw){G5RwH)&__)(!{G5%!)(!Q)(GqR6
Decoded : The wheels on the bus go round and round. round and round.round and round. The wheels on the bus go round and round, all through the town!

CAESAR SHIFT
Key: 5
Plaintext: The wheels on the bus go round and round. round and round.round and round. The wheels on the bus go round and round, all through the town!
Cipertext: Ymj`2mjjqx`ts`ymj`gzx`lt`wtzsi`fsi`wtzsi@`wtzsi`fsi`wtzsi@wtzsi`fsi`wtzsi@`Ymj`2mjjqx`ts`ymj`gzx`lt`wtzsi`fsi`wtzsi$`fqq`ymwtzlm`ymj`yt2s&
Decoded : The wheels on the bus go round and round. round and round.round and round. The wheels on the bus go round and round, all through the town!

Conclusion
maketrans is awesome :)

Python: Cryptography Substitution Cipher improving on the Caesar cipher

Dec 22 09
by mat

This post builds upon the Caesar shift presented previously; converting it to a full substitution cipher. The substitution cipher will practically remove bruteforce style methods of defeating the encryption and provide a basis for more complicated ciphers.

Subsitution Cipher
Because a Caesar shift only rotates the alphabet there are only 25 possible unique solutions, this leaves the cipher quite vulnerable to brute force. If rather than just rotating the alphabet and keeping it ‘linear’ we can shuffle it to create a substitution cipher. This improves the number of possible solutions to a shocking
(26! – 1) = 4.03291461126605635584e26 (unfortunatly, the substitution cipher is alot weaker than it seems as it is vunerable to several different cryptanalysis attacks).

Substitution Cipher Diagram

Substitution Cipher Diagram

We start with the simple Caesar shift function with the following changes:

  • A new array is introduced filled with the numbers 0 – the length of the alphabet. This array is shuffled using shuffle from the random module. The alphabet substitution dictionary is created using this array to decide which letters go where (this is probably clearer in the code than in my explanation).
  • With the Caesar shift we only needed to know the number of rotations in order to decrypt the text, now we need a full list of the letter substitutions. This is stored as the key and will be needed in order to decode our substitution cipher.
  • We also now store the alphabet outside of the function so that it can be used in a decode function. This function was added along with some example usage to make the full process more understandable
from random import shuffle

alphabet="abcdefghijklmnopqrstuvwxyz"

def substitution(alphabet,plaintext):

	# Create array to use to randomise alphabet position
	randarray=range(0,len(alphabet))
	shuffle(randarray)

	key=""

	#Create our substitution dictionary
	dic={}
	for i in range(0,len(alphabet)):
		key+=alphabet[randarray[i]]
		dic[alphabet[i]]=alphabet[randarray[i]]

	#Convert each letter of plaintext to the corrsponding
	#encrypted letter in our dictionary creating the cryptext
	ciphertext=""
	for l in plaintext:
		if l in dic:
			l=dic[l]
		ciphertext+=l
	for i in alphabet:
		print i,
	print
	for i in key:
		print i,
	print
	return ciphertext,key


# This function decodes the ciphertext using the key and creating
# the reverse of the dictionary created in substitution to retrieve
# the plaintext again
def decode(alphabet,ciphertext,key):
	
	dic={}
	for i in range(0,len(key)):
		dic[key[i]]=alphabet[i]

	plaintext=""
	for l in ciphertext:
		if l in dic:
			l=dic[l]
		plaintext+=l

	return plaintext

# Example useage
plaintext="the cat sat on the mat"
ciphertext,key=substitution(plaintext)
print "Key: ", key
print "Plaintext:", plaintext
print "Cipertext:", ciphertext
print "Decoded  :", decode(ciphertext,key)

Running this will output the following (This will be different on each run due to the use of random to generate the key).

Key: miylbsowutgdkfvjepqhazrncx
Plaintext: the cat sat on the mat
Cipertext: hwb ymh qmh vf hwb kmh
Decoded : the cat sat on the mat

Improvement by using additional characters
Adding additional characters into the substitution will it more difficult to solve. For example if we change our alphabet from:

alphabet=”abcdefghijklmnopqrstuvwxyz”

If we include capital letters, numbers from 0 -9 and special characters:

alphabet=”ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890″+ \
“:.;,?!@#$%&()+=-*/_<> []{}`~^”+ \
“abcdefghijklmnopqrstuvwxyz”

We increase the number of possible solutions from (26!-1) to (63!-1) which is 1.98260831540444006412e87. This also has the added benefit of making the encrypted text alot cooler and harder to guess at by eye (unfortunately still very easy to see what character represents space).

Key: MXjAarLzWqFePI7E botO5f1kym29RZd3Sh8JTiQGKVDp6YBCsU4nucNgwlx0vH
Plaintext: this plaintext will be much more of a challenge to decode compared to the Caesar shift cipher
Cipertext: tzWoHEeMWIta1tHfWeeHXaHPOjzHP7baH7rHMHjzMeeaILaHt7HAaj7AaHj7PEMbaAHt7HtzaHjMaoMbHozWrtHjWEzab
Decoded : this plaintext will be much more of a challenge to decode compared to the caesar shift cipher

Future
The substitution cipher is a lot more secure than Caesar shift cipher but unfortunately is very insecure towards frequency analysis. In future posts I will address using frequency analysis and methods to prevent this type of attack as well as improving on this cipher by creating multiple-dicitionary based ciphers to create Vigenère style ciphers.

I imagine most people reading this will enjoy the simple challenge of solving some encrypted text. I have used this code to make some ciphertext, try and decode it! (extra points for knowing where it is from):

^’VtuBbtv3vut1u-w.G^’Vt&vnu-tZBtZnuIvwvtwn
-qbtuB6GN3vutbqBS-qt.BSt&wB~vtV.tqv1wbG}u5t
~nDDv5tVvG}u5tbBwvtVvtbBt@nvIvZG}u5tbqwv6tv
3vw.t@nvIvtnubBt1tUnwvG}Ztbqv.t&Swuv5tnbtqS
wbt&vI1SZvt^t61ZtZBtq1@@.tUBwt.BSm)B6tbqvZv
t@BnubZtBUt51b1tV1~vt1t&v1SbnUSDtDnuvG}u5t6
v’wvtBSbtBUt&vb1GQv’wvtwvDv1Znu-tButbnVvG

(note: newlines were placed to make it fit and do not represent a character)

Update: Made code a little cleaner by moving dictionary outside of functions.

Python: Cryptography Caesar shift encryption (shift cipher)

Dec 21 09
by mat

I have always had a keen interest in cryptography and rather than give a brief history of cryptography I will recommend reading Simon Singh’s The code book or for a modern and hands on approach Applied Cryptography by Bruce Schneier (Who also made a brilliant book on security, more of descriptive approach but very interesting Secrets and Lies: Digital Security in a Networked World).

This post aims to detail the creation (in python) of one of the simplest forms of encryption; the simple Caesar shift (or shift cipher). The Caesar shift takes the normal alphabet and maps it to a an identical alphabet with a rotation. The cipher will be written in such a way that it can be easily expanded on to create more complex encryption schemes with little modification.

Caesar shift alphabet

Caesar shift alphabet diagram

The above image shows a diagrammatic representation of a Caesar shift of 3 (alphabet transposed onto a rotation of itself with a displacement of 3). Below shows the entire alphabet in plaintext and in ciphertext, followed by a simple sentence in plaintext and in cipher text.

Plaintext: abcdefghijklmnopqrstuvwxyz
Ciphertext: defghijklmnopqrstuvwxyzabc
Plaintext: the cat sat on the mat
Ciphertext: wkh fdw vdw rq wkh pdw

Below is the code to convert plaintext into ciphertext along with an example of the usage:

def caesar(plaintext,shift):

	alphabet=["a","b","c","d","e","f","g","h","i","j","k","l",
	"m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

	#Create our substitution dictionary
	dic={}
	for i in range(0,len(alphabet)):
		dic[alphabet[i]]=alphabet[(i+shift)%len(alphabet)]

	#Convert each letter of plaintext to the corrsponding
	#encrypted letter in our dictionary creating the cryptext
	ciphertext=""
	for l in plaintext.lower():
		if l in dic:
			l=dic[l]
		ciphertext+=l

	return ciphertext

#Example useage
plaintext="the cat sat on the mat"
print "Plaintext:", plaintext
print "Cipertext:",caesar(plaintext,3)
#This will result in:
#Plaintext: the cat sat on the mat
#Cipertext: wkh fdw vdw rq wkh pdw

Explanation
Here we have written a function that is given the plaintext and an arbitary rotation (including negative) and returns a ciphertext. The function creates a dictionary, mapping each letter to another letter that is ‘shift’ letters away from it in the alphabet (the modulus (%) is used so to wrap the alphabet back to the start if it falls off the end). It then converts each letter of the plain text into the corresponding encrypted letter using the dictionary.

Future
In the next post I will discuss methods to improve the Caesar shift and how to turn it into a full substitution cipher (where the alphabet is shuffled rather than rotated). The Caesar shift is very susceptible to brute forcing and frequency analysis which I shall explain and create a program to defeat these encryptions in a future post.