algorithms - Dave's Blog


Tweet from David_Risney

2015 Apr 2, 10:43
Tesla's April fools headline fooled stock trading algorithms causing $1.50 jump: …

Stripe CTF - Level 7

2012 Sep 13, 5:00

Level 7 of the Stripe CTF involved running a length extension attack on the level 7 server's custom crypto code.


def logs(id):
rows = get_logs(id)
return render_template('logs.html', logs=rows)


def verify_signature(user_id, sig, raw_params):
# get secret token for user_id
row = g.db.select_one('users', {'id': user_id})
except db.NotFound:
raise BadSignature('no such user_id')
secret = str(row['secret'])

h = hashlib.sha1()
h.update(secret + raw_params)
print 'computed signature', h.hexdigest(), 'for body', repr(raw_params)
if h.hexdigest() != sig:
raise BadSignature('signature does not match')
return True


The level 7 web app is a web API in which clients submit signed RESTful requests and some actions are restricted to particular clients. The goal is to view the response to one of the restricted actions. The first issue is that there is a logs path to display the previous requests for a user and although the logs path requires the client to be authenticatd, it doesn't restrict the logs you view to be for the user for which you are authenticated. So you can manually change the number in the '/logs/[#]' to '/logs/1' to view the logs for the user ID 1 who can make restricted requests. The level 7 web app can be exploited with replay attacks but you won't find in the logs any of the restricted requests we need to run for our goal. And we can't just modify the requests because they are signed.

However they are signed using their own custom signing code which can be exploited by a length extension attack. All Merkle–Damgård hash algorithms (which includes MD5, and SHA) have the property that if you hash data of the form (secret + data) where data is known and the length but not content of secret is known you can construct the hash for a new message (secret + data + padding + newdata) where newdata is whatever you like and padding is determined using newdata, data, and the length of secret. You can find a script on VNSecurity blog that will tell you the new hash and padding per the above. With that I produced my new restricted request based on another user's previous request. The original request was the following.

The new request with padding and my new content was the following.
My new data in the new request is able to overwrite the waffle parameter because their parser fills in a map without checking if the parameter existed previously.


Code review red flags included custom crypto looking code. However I am not a crypto expert and it was difficult for me to find the solution to this level.

PermalinkCommentshash internet length-extension security sha1 stripe-ctf technical web

Line Simplification

2012 Jun 3, 12:47

Neat demo of Visvalingam’s line simplification algorithm in JavaScript applied to a map of the US.

To simplify geometry to suit the displayed resolution, various line simplification algorithms exist. While Douglas–Peucker is the most well-known, Visvalingam’s algorithm may be more effective and has a remarkably intuitive explanation: it progressively removes points with the least-perceptible change.

PermalinkCommentsline-simplification demo technical javascript

C++ Algorithms: next_permutation()

2012 May 4, 1:56

Breakdown of the STL’s implementation of next_permutation.  Ever wondered how that works?

PermalinkCommentstechnical stl c++ algorithm permutation math programming

MapReduce Patterns, Algorithms, and Use Cases

2012 Feb 10, 3:42PermalinkCommentstechnical map-reduce programming howto

Lifetimes of cryptographic hash functions

2011 Jun 20, 11:25A cautionary tale in chart form: lesson is make sure you can always upgrade your hashing algorithm or don't have security dependencies on hashing algorithms.PermalinkCommentsreference hash encryption security table technical humor

Amazon’s $23,698,655.93 book about flies

2011 Apr 27, 2:21Competing price setting algorithms create a very high priced book. "But Peter Lawrence can now comfortably boast that one of the biggest and most respected companies on Earth valued his great book at $23,698,655.93 (plus $3.99 shipping)."PermalinkCommentshumor internet blog science book commerce ad » Blog Archive » Using genetic algorithms to find Starcraft 2 build orders

2010 Nov 8, 3:31Genetic algorithm finds awesome SC2 build orderPermalinkCommentsai algorithm blog code videogames game starcraft2 sc2 genetic-algorithm

Google Prediction API - Google Code

2010 Aug 13, 11:46RESTful machine learning API from Google... "The Prediction API implements supervised learning algorithms as a RESTful web service to let you leverage patterns in your data, providing more relevant information to your users. Run your predictions on Google's infrastructure and scale effortlessly as your data grows in size and complexity."PermalinkCommentsrest ai google programming analysis machine-learning development technical

Gamers beat algorithms at finding protein structures

2010 Aug 4, 2:29Using games for good! Foldit players are solving real biochemistry problems. "Scientists have turned to games for a variety of reasons, having studied virtual epidemics and tracked online communities and behavior, or simply used games to drum up excitement for the science. But this may be the first time that the gamers played an active role in producing the results, having solved problems in protein structure through the Foldit game."PermalinkCommentsvideogame game biology science research

RFC 5843 - Additional Hash Algorithms for HTTP Instance Digests

2010 Apr 21, 6:51Adds SHA 256 & 512 to HTTP instance digest: 'The IANA registry named "Hypertext Transfer Protocol (HTTP) Digest Algorithm Values" defines values for digest algorithms used by Instance Digests in HTTP. Instance Digests in HTTP provide a digest, also known as a checksum or hash, of an entire representation of the current state of a resource. This document adds new values to the registry and updates previous values.'PermalinkCommentshash cryptography http instance-digest sha security technical ietf rfc standard

linkiblog | How to Build a Popularity Algorithm You can be Proud of

2009 Sep 9, 5:49PermalinkCommentstechnical statistics algorithms howto social tutorial math popular reddit digg programming

Web addresses in HTML 5

2009 Mar 23, 11:06The HTML5 spec tells us how it is in the real world for URLs: "This specification defines various algorithms for dealing with Web addresses intended for use by HTML user agents. For historical reaons, in order to be compatible with existing Web content HTML user agents need to implement a number of processes not defined by the URI and IRI specifications [RFC3986], [RFC3987]."PermalinkCommentshtml html5 url uri reference w3c

The igraph library for complex network research

2008 Nov 5, 3:55A graphing library which includes variaous graph visualization algorithms. GNU licensed. "igraph is a free software package for creating and manipulating undirected and directed graphs. It includes implementations for classic graph theory problems like minimum spanning trees and network flow, and also implements algorithms for some recent network analysis methods, like community structure search."PermalinkCommentsreference free development programming visualization graph math library opensource c++ igraph graphviz via:mattb

Deriving a Non-Recursive Fibonacci Function Using Linear Algebra

2008 Aug 20, 10:51

In my Intro to Algorithms course in college the Fibonacci sequence was used as the example algorithm to which various types of algorithm creation methods were applied. As the course went on we made better and better performing algorithms to find the nth Fibonacci number. In another course we were told about a matrix that when multiplied successively produced Fibonacci numbers. In my linear algebra courses I realized I could diagonalize the matrix to find a non-recursive Fibonacci function. To my surprise this worked and I found a function.
The Nth Fibonacci value is (1 + sqrt(5))^N - (1 - sqrt(5))^N all over sqrt(5) * 2^N
Looking online I found that of course this same function was already well known. Mostly I was irritated that after all the algorithms we created for faster and faster Fibonacci functions we were never told about a constant time function like this.

I recently found my paper depicting this and thought it would be a good thing to use to try out MathML, a markup language for displaying math. I went to the MathML implementations page and installed a plugin for IE to display MathML and then began writing up my paper in MathML. I wrote the MathML by hand and must say that's not how its intended to be created. The language is very verbose and it took me a long time to get the page of equations transcribed.

MathML has presentation elements and content elements that can be used separately or together. I stuck to content elements and while it looked great in IE with my extension when I tried it in FireFox which has builtin MathML support it didn't render. As it turns out FireFox doesn't support MathML content elements. I had already finished creating this page by hand and wasn't about to switch to content elements. Also, in order to get IE to render a MathML document, the document needs directives at the top for specific IE extensions which is a pain. Thankfully, the W3C has a MathML cross platform stylesheet. You just include this XSL at the top of your XHTML page and it turns content elements into appropriate presentation elements, and inserts all the known IE extension goo required for you. So now my page can look lovely and all the ickiness to get it to render is contained in the W3C's XSL.

PermalinkCommentstechnical mathml fibonacci math

GRDDL Primer

2006 Nov 28, 3:24GRDDL is a mechanism for Gleaning Resource Descriptions from Dialects of Languages. It is a technique for obtaining RDF data from XML documents and in particular XHTML pages. Authors may explicitly associate documents with transformation algorithms, typicPermalinkCommentsreference w3c web xml rdf metadata grddl semanticweb

Rarest First and Choke Algorithms Are Enough

2006 Aug 31, 7:44More Torrent research. This is a paper describing performance of BitTorrent's block and peer selection algorithms.PermalinkCommentsp2p torrent report reference internet algorithm performance

Dictionary of Algorithms and Data Structures

2005 Dec 29, 3:15The National Institute of Standards and Technology's Dictionary of Algorithms and Data Structures, including some implementationPermalinkCommentsreference development algorithm software tools dictionary search
Older Entries Creative Commons License Some rights reserved.