GSoc Idea: New Hash Function for Hash Table Processing

New Hash Function for Hash Table Processing

Areas C algorithms, security
Good if student knows Tcl, C
Priority Medium
Difficulty medium to high
Benefits to the student learn about application of basic algorithm concepts to practical problems
Benefits to Tcl Improved performance and security in core
Mentor ?

Project Description

Like most dynamic languages, Tcl uses hash tables for tasks like array lookups. And like most dynamic languages, Tcl is vulnerable to an attack (in programs that accept user input) that has received significant press recently: a hash table collision attack [2 ] [1 ]. Some attempts were made years ago to implement a new internal hash function which would eliminate the vulnerability, but due to performance problems perceived by some parties, the attempts were dropped.

In recent years, new hash functions have been developed which in some cases show better performance as well as better security than previous algorithms; such as MurmurHash, SpookyHash and CityHash [3 ].

The goal of this project would be to evaluate different hash algorithms for potential suitability for inclusion in the Tcl core as replacement for existing hash generation code. The ideal replacement would show both better performance and better security. The ultimate goal would be for this project's code to be accepted into the Tcl core.

SEH: I submit this idea as an interested consumer, not a domain expert. Perspectives have been gleaned from conversations with others who should know better. Requires a qualified mentor, probably a core team member.

Requirements:

Knowledge of:

  • C programming
  • Multi-platform development
  • Performance testing