Hacking

This is part two of the summary from the Day 1 of the workshop.

There were lots of good talks today at the workshop. I will highlight some of them:

Nadia Heninger from Microsoft Research discussed the dangers in bad key generation, along the same lines of the talk from yesterday by Jesse Walker (Intel). She showed that from a list of published certificates there are ~1% of completely hackable ones (meaning that you can find the private keys easily). These are either because they share a prime (and then factorizing is trivial) or they have the same public key. Interesting to hear that they noted the companies that have bad keys, but not all of them responded.

Ben Adida (Mozilla) gave an interesting talk about Persona. It is an open authentication platform that uses emails to authenticate, but unlike others (e.g., Facebook Connect), Persona does not learn the websites the user visits/authenticates. It is very easy to integrate for website authors (only JS is needed), and preserves users' anonymity, so it's pretty cool (not sure how well it will catch, though...perhaps when the Firefox phones will be out?).

Adam Langley's (Google) talk was very interesting, and he tried to inform researchers about the things they care most in the industry. Amongst these:

"Create a splash", meaning, make noise so that identified problems will be noticed by the community and not buried in a paper.

Notify the companies (let them know before publishing the problem, always publish code alongside with algorithms. As an example he gave AES, that has so many bad implementations out there, that it is almost impossible to know what each leaks.

If your algorithm runs slow now, using Moore's law and saying that it will run faster on future processors is nonsense, because in the future there will be more data that it will need to process. He summarized this by saying: "if it's crap now, it will be crap in the future".

Always design algorithms in constant time, to mitigate side-channel attacks.

Also provide designs on a budget - meaning, you can specify a very sophisticated algorithm, but these are commonly expensive to fully implement and deploy. In such cases, it is a good idea to also propose budgeted designs, that are perhaps a bit weaker, but are deployable.

  The final talk by Eric Rescorla (RTFM) was mostly about deployment of TLS, showing the difficulty to deploy updates in the wild. He showed an interesting plot of the rate of certificate replacement given that they are known as broken, as opposed to timely replacement (due to expiration). It takes around 150 days to replace 50% of the certificate, in *both cases*. So people are not really worried about fixing stuff. IE7 is still common, with all its known bugs. TLS is still deployed with the older RC4 cyphers (also in Google, Amazon, Wells Fargo. 

The talk gave an interesting perspective about real-world deployability of crypto innovations, and how difficult it is to actually push updates, even if they fix real security risks.

Attending the Real-world Cryptography Workshop, and will summarize some of the cool talks.

You can also read the summary of some interesting talks from the second day.

Jesse Walker, Intel

First talk by Jesse Walker (Intel) - gave a cool example how generating random numbers fails in real-world deployments. In a production facility, Intel engineers need to create an RSA certificate, so they use OpenSSL for that. While OpenSSL seems to be working well, the engineers first set the time to some fixed date in 1970, and then sampled the clock to create a "random" value.

Obviously, this is a very bad implementation, and Jesse emphasized the need to explain engineers that we need "ignorant sources" (rather than "high entropy"), and it is possible to come up with application-level models that are pretty good. One example he should (which is not really portable but works reasonably well), is to sample the time it takes to execute a system call. 

Jesse emphasized the need to have good random sources that are verifiable by a model that can validate the correctness of the harvested bits.

  Nick Mathewson (Tor)

Talk about (some) crypto aspects of Tor. Tor hides client-server web access by using a network of Relays and Exit points (~3000 relays), 500K users a day, carring more than 2GiB/sec. This helps overcome cencorship and enable annonimity. 

Initially (~2002) Tor didn't get lots of attentions from the crypto community. Now things change. Tor uses TLS for connections. TLS has lots of variants and it is easy to detect the variant based on the cipher choice, certificates and extensions. However, the more secure variants are less common.

Funny things is that the less common variants are blocked by goveremnets (because they are rare, blocking all of them don't cause too much damage). So if Nick implements some new TLS standard it is commonly blocked by censoring-govs (e.g., China), basically "killing the feature" for any valid implementation in the country.

Tor does one-way key-exchange based on state-of-the-art. What Nick suggests is that the best implementation is based on the tweaks you can do to accelerate the execution, like parallalizing exponentiation. He believes there is more possible speed-ups.

  Jon Katz (U. Maryland)

Provide authenticated service to users while preseving their annonymity, and not allowing them to share their credentials with other users. To this end, the server cannot link a "login event" with a "registration event" and also cannot link different "login events" with each other. The server should accept (valdate) a login, but cannot assign this login to a user. However, each user can only have one active login at a given time (per "epoch").

Lots of technical details in the talk (paper is under submission), but they use interesting tools to implement their techniques:

http://crypto.stanford.edu/pbc/

https://polarssl.org/

  Juan Garay - iDecrypt (AT&T)

Want to tackle the problem of "shoulder surfing" - neighbors looking at your screen while you are doing stuff. There are hw solutions that attach to the screen and polarize the light so you need to sit in front of the screen. This work is looking at crypto solutions to this problem. They propose two main components - visualizable encryption scheme, and new visual encoding techniques - both should work for recorded content as well as streaming content.

There are a bunch of visual encoding schemes, however, these guys wanted locality and relative positioning abilities, so that in order to encode/decode you don't need the complete image. He showed a (non-live) demo of an iPhone app that uses the camera for decrypting a picture and shows the decrypted image on the screen. Problem is that it takes 4-5 seconds for a single image. Interestingly, they want to use the GPU of the phone to speed up things.

Thing is that the value of this is not clear to me. If this can be acheived by low-cost hardware (polarizing screen), then why do all the effort? what is the added value of doing this with crypto and visual encoding, if the end result is the same (only with lower quality??).

  Raluca Ada Pop - CryptDB (MIT)

A nice concept of encrypting a DB and operating on the encrypted data. Since FHE is non pratical, CryptDB offers layers of protection, enabling efficient computations depends on what the query is. For summation it uses SHE, for equality comparison it uses simple encryption and for all other comparisons it offers order-preserving encryption. Then it peels the layers based on the query. The implementation uses a proxy to make executing completely transparent for the user.

Although cool, in face of active adversary, all the layers are not that useful, because these are easily peeled, and then it boils down to the weakest encryption scheme that they use. Nevertheless, it is a nice proof of conecept towards computing on encrypted data in real-world scenarios.

In case of a DNS outage, we're doomed.

Nowadays, when almost everyone uses hosted services (EC2, AppEngine, Heroku, etc.) it seems quite obvious, but I wanted to check it anyway and conclude - if you think that using IP address instead of the domain name will get you far, you're wrong. In fact, almost 40% of the top-1000 websites (ala Alexa) in the Internet return a completely different page when you use the IP address to access them and when you use the domain name. These include most Google services (except search), Wikipedia, WordPress (including TechCrunch), Engadget, eBay and others. Some of these return a funny page, some a broken page and others -- just a strange looking page. If you want to be an optimistic, then 60% of these website do work the same if you use the IP address, however, to cool things down, many of these are just localized versions of the same website (www.google.de, www.google.fi, www.google.co.hu, etc.), so the actual percentage is lower. 

Background. 

Very short - when you issue a GET request to a domain (e.g., by browsing to the website), the domain name is first resolved to an IP address of the server using a DNS server. Then, a TCP socket is opened to the resolved IP address, and an HTTP GET request is sent. The HTTP request includes a (mandatory) HOST header, that tells the receiver which host was originally requested. This enables shared cloud hosting, virtualization, CDNs, reverse proxies, application firewalls etc. When you browse directly to the IP address, the server has no way to determine the original domain that was requested, so if several services are hosted using the same IP address, the server has no way to determine which one should be served. 

Method.

I took Alexa's top 1000 websites, and wget all of them (from the US), one after the other, using their domain name. When you do a wget using a domain name, it first performs an nslookup, shows the list of IP addresses and does the actual GET request to the first IP address. For each of the IP addresses it showed, I did another wget.

I repeated this for roughly 100 times for each website, and computed, for each website, the average page size when using the name and when using the IP address. The assumption here is that if the page size is significantly different (more than 5Kbytes difference), then the result is different. This method has some caveats, but they mostly result in this analysis providing a lower-bound to the problem.

Results.

The following plot shows the average page size for each website when using the IP (x-axis) and when using the domain name (URI, y-axis). On the diagonal are all the pages that behave the same. All others (colored in green) are those that result in different sizes.

A few interesting findings:

The google search engine works fine when using IP address. However, other Google websites refer to the google main search page. These include youtube.com (e.g., 74.125.224.137), blogspot.com (173.194.79.191), android.com (74.125.224.38), mail.google.com (74.125.224.149). It makes sense that all google products are hosted on the same servers, and then routed based on the requested host.

Wordpress treats the IP address as if it is a standard host name and breaks. Try to browse to 66.155.9.238. I guess it parses the first "." as the subdomain, and then it shouts that "66.wordpress.com doesn't exist". This also means that techcrunch.com is gone.

Even more surprising is the response you get from browsing eBay using one of its IP address (e.g., 66.135.200.181). You'll get a completely broken page, with a bad CSS and a "Page Not Responding" title. eBay - please fix this.

There goes wikipedia...try to visit the IP address (208.80.154.225) and you'll get an "Unconfigured domain" page.

If you go to the IP of msn.com (131.253.13.140), you land on bing.com. Much better looking.

StackExchange has a nice page. Try to visit 69.59.197.21 and see a good example to a graceful error page.

Conclusions.

This is a common problem. You have a file that contains ratings that users give to items. Usually, the file has many rows that look like:

user_id, item_id, score

Sadly, the users ids and the item ids are often not consecutive or on a zero-based indexing. When you want to read something like that into a sparse matlab or octave sparse matrix, you need to convert it to a zero-based indexing scale. Here is how to do it with a one-liner awk script:

$ cat ratings.txt | awk -F"\t" 'BEGIN {u_c=1; i_c=1;} { if (!u[$1]) {u[$1]=u_c; u_c++;};  if (!i[$2]) {i[$2]=i_c; i_c++;}; print u[$1],i[$2],$3;}' > zero_index_ratings.txt

The collection lib has many cool classes, like defaultdict. Basically it is a dict that you can initialize with some value, so you don’t need to check if the key exists before each assignment, such as the following annoying computation of histogram: d={}

if item not in d:    

  d[item]=0 d[item]+=1

can be easily replaced with: from collections import defaultdict d=defaultdict(int) d[item]+=1

The cool thing is that you can give arbitrary “default factories”, that are simply a function without parameters. So let’s say you want to have a dict, with each key holding a list of three elements, all initialized to zero: d[k]=[0,0,0] d=defaultdict(lambda: [0,0,0]) d["hello"][1]+=1

Or you can even have a nested defaultdict, if you want double indirection: d = defaultdict(lambda:defaultdict(int)) d["hello"]["world"]+=1

Say that you have a link of an image that shows text, and you want to extract the text (i.e., run OCR on it). Instead of running the OCR locally, there are a bunch of servers with a very easy API (WeOCR) that enable pretty good OCR with a wide range of algorithms. 

Most of these servers run Tesseract-OCR (or OCRAD, or other modules), most of which you can download and run locally (and it also has python bindings). However, I've noticed that the results of some of the WeOCR servers are better than home-brew tesseract execution, probably since they fine-tune the parameters, or improve the trainings of the algorithm. Different servers also provide various functionalities and tune-ups, like supporting multiple languages, low-quality photos, multi-line inputs etc. 

Notice that to find the cgi link for a server, you need to go the the server spec (example here), and view the source of the file. In the source, look for the "cgi" link.

It turns out that to make this work, you need some steps:

Download the image from the URL into a memory image buffer

[optional] Improve the image quality for OCR analysis

Save the image into a format used by common OCRs

Post the image to the server and get the response.

For this to work you need a bunch of libs. Communicating over HTTP is done with urllib2 (standard in Python). 

Processing the image and saving it into a bmp is done with PIL.

The nasty part is to send the image to the server, as it requires a form-like multipart-related format. However, I used the very cool poster module, that solves this problem in a second (python still doesn't have a built-in support for multipart forms). So here is the code:

import Image from poster.encode import multipart_encode from poster.streaminghttp import register_openers import urllib, urllib2 import StringIO

register_openers()

# You can put whichever server you want. ocr_server= 'http://jimbocho.ocrgrid.org/cgi-bin/weocr/submit_tesseract.cgi'

def get_text_from_image(img_url):

  # download the image into a memory Image object   response = urllib2.urlopen(img_url)   im_data = response.read()   file = StringIO.StringIO(im_data)   im = Image.open(file)   # this improves the image a bit and converts to b/w (not needed if the image is in good quality)   im = im.convert("L").filter(ImageFilter.EDGE_ENHANCE_MORE).convert("1")

  # save the image into a temp bitmap

  im.save("/tmp/temp.bmp")

  # prepare the post command to the ocr server

  datagen, headers = multipart_encode({"userfile":open("/tmp/temp.bmp","rb"), "outputencoding":"utf-8", "outputformat":"txt"})

  request = urllib2.Request(ocr_server, datagen, headers)

  text = urllib2.urlopen(request).read()

  return text

There is room for improvement. Currently the WeOCR servers do not return "nice" error codes. So there is parsing to do. 

Python's sorted function is pretty handy even when it comes to sorting dictionaries. The question of how to sort a dict by value appears tons of time online, and the common answer is to use:

sorted(d.iteritems(), key=lambda (k,v): (v,k) )

The idea is simple. The dict's iteritems() simply returns an iterable set of (key,value) pairs, and the key parameters tells the sorted function to inverse the order (thus it uses the value as the sorting key instead of the key of the dict).

The nice thing is that you can do very cool things when you have more sophisticated dicts that you want to sort. Say that I have a dict of lists, e.g.:

d = { 'a':[1,2,3,4,5], 'b':[5,6,34,2,5], 'c':[2,5,6,7,8] ... }

In my case, I have a set of values (dict keys) and for each value I store a list of confidences obtained from running different algorithms (each algorithm 'votes' for a value and gives it a confidence score). Now I want to find the value that has the 'best' confidence. There are several ways to calculate the 'best' confidence, and I use sorted to find each:

There are a bunch of reasons why MySQL can get hang during startup, and they are listed online (mainly as a result of a strange loop in my.cnf). However, my case was different, and the sad thing is that mysql reported nothing in its log, although the problem was simple:

- In order to give access to the mysql server from different machines, I've changed the bind address in my.cnf to my IP (instead of 127.0.0.1).

- After several weeks, I replaced the router, so instead of 10.x.x.x it now had a 192.168.x.x address.

- When mysql server tries to bind to this address, it hangs, and reports nothing.

useless_files.py Download this file

  When uploading Latex papers for some journal and publication systems (e.g., IEEE explore), you need to upload all the source and figure files. 

I've noticed that often my "figs" folder contains more figs than actually included in the paper, and I want to remove these files. This becomes a taunting task, of looking for figures that I include in the latex, and removing all the files that are not actually included. 

So instead, I wrote this simple script, that goes over a bunch of latex files, and compares the included files with a given folder. So for example, if I have a paper comprised of two latex files called paper.tex and appendix.tex, and I want to see which files from folder "fig" are not included in them, then I simply write:

$ python useless_files.py --recursive --images=./fig paper.tex appendix.tex

The output is the list of (figure) files that appear in folder ./fig and it subfolders (due to the --recursive flag), and for each file, the number of times it appears in the latex files. Files that do not appear, should probably be removed from the figs folder.

Some other useful tags:

--images - specify the folder of the figures

--full-path - use full path in file names

--use-ext - use the extension of the file when looking for the file name

--image-types - comma separated list of file types to look for in the figure folder (default .eps,.jpg,.pdf,.png).

cdf_plot.py Download this file

  I was searching for a matlab cdfplot in pylab but couldn't something which is as simple as the one matlab has. So I ported the one matlab has to numpy and pylib, and it turned out quite nice.

Attached is the code for the cdf_plot. It's very easy to use, simply create a numpy array and cdf_plot it. Also, it has a __main__ so you can run it and see it works.

For example, the following plots a simple CDF plot of an array:

python

$ import numpy

$ import cdf_plot

$ x=numpy.array([1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8, 9])

$ cdf_plot.cdf_plot( x )

A cool feature that does not exist in matlab, is the ability to add markers in specific values. This is simply by adding a "values" key in the parameters list:

$ cdf_plot.cdf_plot( x, values="2:rx,4:bo" )

Matplotlib trendline

  Drawing a trendline of a scatter plot in matplotlib is very easy thanks to numpy's polyfit function.

Most of the code below is taken from http://docs.scipy.org/doc/numpy/reference/generated/numpy.polyfit.html. 

Polyfit minimizes the squared error and can find a line or any higher-degree polynomial fit, as specified by the third argument.

Assuming we have a scatter of two vectors - x and y. 

# plot the data itself

pylab.plot(x,y,'o')

# calc the trendline (it is simply a linear fitting)

z = numpy.polyfit(x, y, 1)

p = numpy.poly1d(z)

pylab.plot(x,p(x),"r--")

# the line equation:

print "y=%.6fx+(%.6f)"%(z[0],z[1])

The attached plot provides the average pagerank (http://en.wikipedia.org/wiki/PageRank) of several ASes (http://en.wikipedia.org/wiki/Autonomous_system_(Internet)) over time. You can see the trendline for each set of scatter plots. 

You can easily use this method for any higher degree fitting. For example, a parabolic fit will be:

z = numpy.polyfit(x, y, 2)

Matplotlib uses filled opaque markers as default. Turns out that it is quite easy to make them unfilled and transparent.

pylab.plot( x,y, "o", markersize=7,

markeredgewidth=1,markeredgecolor='g',

markerfacecolor='None' )

Took me some time to find it. The trick is to use markerfacecolor="None" as opposed to markerfacecolor=None (notice that the " are gone). The latter produces the default settings (filled markers) whereas the first produces unfilled transparent markers.

If you use markerfacecolor="w", then it will turn out white, which may look ok, but it is opaque and not transparent. 

The strange thing is that if you try to give the color using the standard method, like "ro" (red 'o' marker) it will not be red when you add the markerfacecolor="None", but instead will be black. Not sure why is that, but fixing it is very easy with the markeredgecolor='r' setting. 

create_tile.py Download this file

This script creates a tile of images from a given folder or a set of files.

Simply pass the folder name (or files), the number of images on the x and y axes and the requested thumbnail size.

Quite easy to use, requires Python and PIL (sudo apt-get install python-imaging).

Yep, this sounds a bit strange - a single process pool? why would you need this??

What happened to me is that I wrote several scripts that use the (excellent) multiprocessing package for the very easy creation of a process pool.

from multiprocessing import Pool

The thing is that on some platforms, it does not run well. 

Not sure why is that, but I get an Issue 3770 (which should be closed http://bugs.python.org/issue3770) on a virtual machine, which basically means that I cannot use multiple processes using the process pool. Since I just want the same code to work on this vm, I wrote a simple class that mimics some of the functionality of the Pool:

class SingleApplyResult(object):

        def __init__(self,v):

                self.value=v

        def get(self):

                return self.value

class SingleProcessPool(object):

        def __init__(self):

                pass

        def apply_async(self, func, args=(), kwds={}, callback=None):

                value = func(*args, **kwds)

                return SingleApplyResult(value)

        def close(self):

                pass

        def join(self):

                pass

def get_pool( processes, force_singlethread=False ):

        try:

                if force_singlethread:

                        pool=SingleProcessPool()

                else:

                        pool=Pool(processes=processes)

        except:

                print "failed getting multi-process pool, getting single-process"

                pool=SingleThreadPool()

        return pool

That's it. When I want to create the pool, I just write:

pool = get_pool(processes=20)

and it gives me a pool which either supports many processes, or just one if the platform does not support it.

image_distorter.py Download this file

  Recently, I had to randomly apply distortions to images. Luckily, I found Python Image Library (PIL).

You can download and read all about it in: http://www.pythonware.com/products/pil/

If you installed setuptools (sudo apt-get install python-setuptools) then you can just write:

sudo easy_install PIL

The script (needs at least python2.6) randomly distorts images from a source folder into a target folder, keeping the original name from the source folder. This is useful when you want to run various algorithms on the images and be able to easily compare the results of the original image and the distorted image. 

To use the script, simply provide the source and target folders and the set of distortions you wish to apply on each images. 

The randomness is hard-coded, so if you want to change it, you need to manually edit the code. 

For example, if you specify --rotate, then it will do a random rotation of up to plus or minus 5 degrees. If you want to change it, you need to edit the file.

You can play with many distortions, such as --smooth, --brightness, --contrast, --rotate, --sharpness, --color, --blur, --posterize, --resize. 

Simply run the script without arguments to see all options.

A simple example would be (rotates and crops):

python image_distorter.py images_orig/ images_rotd/ --rotate --crop

Other than that, the script uses two very cool python modules - OptionsParser and mutliprocessings. 

The first gives an excellent method for command line argument parsing.

image_ripper.py Download this file

I've wrote a little script that downloads images from Google or Bing and stores them into a local folder. It's python so it should work on all OSes, but I only tested it on Linux (Ubuntu 10.4).

Notice that it uses the AJAX API, so Google only allows 32 images and Bing requires an AppID (just create one in the bing developers site). Google recommends, but does not require.

Just run "python image_ripper.py" to see the options and syntax. Basically, you need to give the query string (should be in quotes) if more than one word, and a target folder for downloading. So something like:

python image_ripper.py --workers=50 "space shuttle" ~/images/space_shuttle

should give you 50 worker threads that download images from Google. Same thing with --bing will do the same from Bing, only you will also need to specify the --key=xxxx.

Some conferences require that the camera ready version of an accepted paper will have all fonts embedded. For some reason, matlab (and some other applications like PowerPoint and Visio) do not embed all fonts when creating .eps figures. Not sure why. However, I found two ways to create a pdf with embedded fonts.

1. Convert the .eps images to .pdf and then use pdflatex to generate the pdf. When converting the eps to pdf you should have the following tags sets: -dSAFER -dPDFSETTINGS=/prepress -dNOPAUSE -dBATCH -dUseFlateCompression=true -sDEVICE=pdfwrite -dCompatibilityLevel=1.4 -r1200

2. I found the following in http://www.win.tue.nl/latex/faq.html#q18. The explanation is for winedt, but it pretty much does the same of the above and can be adapted to any latex build system. However, in this case you need to create the .dvi, then convert to .ps and then do a ps2pdf. The latter will embed the fonts:

In WinEdt:

Open WinEdt

Select: Options, Execution Modes

Select ps2pdf

Add the following switches to this line:

-dPDFSETTINGS=/printer -dMaxSubsetPct=100 -dSubsetFonts=true -dEmbedAllFonts=true

  btw, I found that ACM have a great site for various problems in preparing LaTeX: