Bath-Salted Password Hashing

Conversations with a Document Store

I stayed up rather late writing some code for my MUD. When I finally went to sleep, I had an interesting dream involving a conversation with the idealized personification of MongoDB.

What the heck? How can one have a conversation with a NoSQL document store? Have you ever seen Transformers: The Movie (1986)? Do you remember the scene where Megatron encounters Unicron?

If you imagine that I was Megatron and MongoDB was Unicron, you won't be far off. However, our conversation was a little less contentious than the one Megatron and Unicron shared.

After I woke up, some of that conversation congealed into a cryptography idea.

Bath-Salted Password Hashing

If the idea turns out to be a good one, then I decided to call it Bath-Salted Password Hashing because it will make password crackers as angry as someone high on bath salts.

If the idea turns out to be a bad one, then people will say I must have come up with it while high on bath salts.

Note: I'm not sure if this idea has been proposed before. I've done some reading on salted password hashes, but I don't remember this proposal. Likely, it has been proposed and shot down as insecure before. If you have experience with cryptography or especially cryptanalysis, I would appreciate your feedback!

Password Storage - The Naive Approach

The problem we are trying to solve (and the problem I was working on with my MUD) is the problem of storing passwords for authentication. You've got a service hosted online and your users have an account registered with the service. You want to make sure that an account is only accessed by users who know a shared secret (i.e.: the password to the account).

So in your database, you store the account name and you store the password in plain text. When someone logs in, you check to see that the password they provided matches with what you have stored in your database.

Account	Password
Alice	Michelle
Bob	bobrulz
Carol	DybubyeaHyd9
Dave	bobsux

This is simple and it works. However, there is a serious drawback to this solution: Every password is stored in plain text. One security breach and every account is instantly compromised. Even worse, people re-use their passwords on multiple services, and so all of those accounts are now compromised too.

Password Storage - The Slightly Better Approach

Instead of storing the password, we decide to store the hash of the password. A hash function is a mathematical function that scrambles up the input and attempts to provides a more-or-less unique value, a kind of fingerprint of the input if you will.

Account	Password
Alice	ee17dc479d8eb9848d89de4ae67b526d
Bob	75ecf6c2761847d6bd1d356f3c4fafcd
Carol	883380925f05df121f930e5fb7e27ced
Dave	052f13c55882109205f02c240132259c

So now when a user provides their password, we run it through the hash function and compare the output. If they match, they've provided the same password and we grant access. If not, we deny them access to the account.

Surely this is much better. If we have a security breach, the attacker can't see the passwords and the day is saved. Or, is it...?

https://duckduckgo.com/?q=ee17dc479d8eb9848d89de4ae67b526d

https://www.google.com/search?q=052f13c55882109205f02c240132259c

A quick search for the hash output gives us Alice's password and Dave's password. Well, that's certainly less than ideal.

Password Storage - The Somewhat Better Approach

I don't know if you've seen The Shield. It was an excellent television show (cop drama) that ran from 2002 to 2008. I watched it up until I moved to India in 2004 and I am just now (5 years on) trying to catch up to where I left off.

In The Shield, there was a scene in Season 2 where Officer Shane Vandrell tells Officer Julian Lowe, "When it comes to your partner's career, the truth is like grits. You don't serve it up plain, you put a little salt on it."

To paraphrase Shane Vandrell:

When it comes to hash functions, passwords are like grits. You don't serve it up plain, you put a little salt on it.

A salt is a bit of random data that you mix with the password before providing it to the hash function. The output then reflects the combination of the password and the salt value. So in our database, we'll generate a random salt for everybody and store it alongside the password.

Account	Salt	Password
Alice	PeksOtt6	2566bb01cdf46637d85c314ca74800c5
Bob	Jagwelv4	413c9255f6df8b2b5d10b8cdf773d3c3
Carol	AvTohon1	f6010835686677d7540b75e3a78be0f4
Dave	topNeum4	0b6c8acd08fa79230c589d75b9974df2

When a user attempts to log in, we look up their salt value, append the provided password and feed that into the hash function. If the output matches, we grant access to the account. If not, we deny access to the account.

But what about a security breach? Try searching for those hash values. As of this writing, they don't lead to any results. (Of course, if Google decides to index this blog post, that'll blow this paragraph straight to hell, won't it?) So the day is saved. Or is it...?

https://en.wikipedia.org/wiki/Password_cracking

As you might guess, even salt is not the end of the story. If we use a simple scheme to salt the password (such as appending the password to a salt value) we make it harder for the attacker to simply look up the password.

However, this does not thwart clever attempts to guess the password by brute force. If an attacker knows that Dave is a high value account (maybe Dave is an administrator on the service and has access to special commands) they would start by computing the hash of the salt:

startingPoint = MD5("topNeum4")


Now they try to brute force Dave's password. Unfortunately, Dave has a rather short password ("bobsux") and it probably won't be long before it is broken.

You might ask: What if we add some more salt? Put some salt on the end of the password? Or in the middle of the password? Will that help?

Yes and no. Salt is not considered to be a secret. The prefix salt can still be used as a starting point, and salt in the middle or at the end just adds a few more computational steps in the cracking process. Here's an interesting article that goes into some more detail on that:

http://www.rhyous.com/2012/06/18/how-to-effectively-salt-a-password-stored-as-a-hash-in-a-database/

So yes, it helps to slow down the attacker a bit. But no, it doesn't provide an order of magnitude more help.

Password Storage - The Current State of the Art

Password-Based Key Derivation Function 2 (PBKDF2) uses several thousands of hash iterations. By applying the hash function repeatedly, the computation resources needed to hash a single password grows quite large.

By estimating the computing resources of the attacker, we choose the number of iterations sufficiently high that testing even a small part of the password space is infeasible.

However, as the Wikipedia article points out, even PBKDF2 can be misused. A single iteration is really no stronger than a single hash. So if you intend to use PBKDF2, make sure that you use it correctly.

Wikipedia also references bcrypt and scrypt as members of this key expansion / key stretching family of salted password hashing algorithms.

Password Storage - Bath-Salted Password Hashing

You're still here? Oh good. This is where we get to the meat of this blog post.

I propose a "new" (at least to me) method of hashing salted passwords. I don't know if it is more secure than existing methods. I don't know if it requires more resources to crack than existing methods. Literally, this idea congealed in my head less than 24 hours ago. I write this post with two goals:

1. Communicate the Bath-Salted Password Hashing algorithm so that anybody could implement it in the language of their choice.
2. Solicit feedback from cryptographers: Is this idea worth considering? Or is it a waste of time for reasons that are currently unknown to me?

Preconditions:

- Given P = a password, N bits in length
- Given X = a prefix salt, at least 2*N bytes in length
- Given Y = a postfix salt, at least 2*N bytes in length
- Given H = a strong hash function (for example, SHA-3 [as of this writing])
- Given I = an empty input buffer

Pseudo-Code Algorithm:


x = 0
y = 0
for i = 0 to (N-1)
  b = P.bit(i)
  if b == 0
    I.push(X[x])
    x++
  else // b == 1
    I.push(Y[y])
    y++
I.push(X.slice(x,X.length))
I.push(P)
I.push(Y.slice(y,Y.length))

output = H(I)
 

Description:

For each bit of the password, we consume a byte of either the prefix salt or the postfix salt, depending on the value of the bit. The byte is appended to the input buffer.

After we have consumed N bytes (taken in an arbitrary order from the two salt values) we append the remainder of the prefix salt to the input buffer.

We then append the password to the input buffer.

We then append the remainder of the postfix salt to the input buffer.

The output is then the result of running the hash function on the input buffer.

Discussion:

The bits of the password are used to select the salt bytes that are used to construct the input buffer. Because the password could have an arbitrary length and bit content, the number of bytes, where they came from, the order in which they will appear will vary significantly between passwords.

Although the salt is not secret, the portion of it that becomes more password-like than salt-like is unknown to the attacker.

A possible improvement would be to run the password (unsalted) through a second distinct hash-function (call it H') to obtain P' and then truncate the number of bits to match the number of bits in the original password. The idea here would be to take a password with a (potentially guessable) lopsided number of 0s and 1s and convert it to something with a more even distribution of 0s and 1s. We truncate to retain the original bit length so as to deprive the attacker the knowledge of a fixed consumption of the salt values.

Iterated Bath-Salted Password Hashing?

I'll admit that I haven't given much thought to iteration yet. But here's sketch of how I might start exploring it:

Let A be the number of iterations to run the password through H' during each iteration of the bath-salt algorithm.

For example, if A=5 then the inner-hash would be P' = H'(H'(H'(H'(H'(P)))))


Let B be the number of iterations to run the bath-salt algorithm

After computing the output of a bath-salt iteration, let Mutate_Index be the (log2(N)+1) bits from the LSB of the output. Mutate (xor 1) the bit at (index % N) of P. Now iterate B-1 more times.

More To Come

Unfortunately, I've already spent more time writing this blog post than I intended. My plan is to follow up next week with more specifics, including a Node / JavaScript / CoffeeScript implementation of these ideas.

Thank you for reading and many thanks in advance for any feedback!

Using Guava EventBus with Spring - Part 2

In my previous post on the topic of Using Guava EventBus with Spring, several smart people pointed out shortcomings in my code sample.

Yvan DeBoeck pointed out that Guava was already doing the work of scanning an object for @Subscribe annotations. So, I reduced that aspect in my code. My scanning is now limited to reporting a warning in the logs, and is only performed on beans that I am not registering with EventBus.

Benjamin Diedrichsen pointed out that EventBus uses strong references. This is a really important tip! Spring will happily generate plenty of non-singleton beans, and giving them to EventBus is a recipe for a memory leak. So, I added an @Autowired reference to the ApplicationContext and use that to verify if a bean is a singleton before calling eventBus.register().

Here is my updated version of EventBusPostProcessor:

/*
 * EventBusPostProcessor.java
 * Author: Patrick Meade
 *
 * EventBusPostProcessor.java is hereby placed into the public domain.
 * Use it as you see fit, and entirely at your own risk.
 */

package com.example.spring.guava;

import com.google.common.eventbus.EventBus;
import com.google.common.eventbus.Subscribe;
import java.lang.reflect.Method;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.beans.BeansException;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.config.BeanPostProcessor;
import org.springframework.context.ApplicationContext;

/**
 * EventBusPostProcessor registers Spring beans with EventBus.
 * @author pmeade
 */
public class EventBusPostProcessor implements BeanPostProcessor
{
    private static final Logger log = LoggerFactory.getLogger(EventBusPostProcessor.class);

    public static boolean containsSubscribe(Object bean)
    {
        Method[] methods = bean.getClass().getMethods();
        for(Method method : methods)
        {
            Subscribe subscribe = method.getAnnotation(Subscribe.class);
            if(subscribe != null)
            {
                return true;
            }
        }
        return false;
    }
    
    @Override
    public Object postProcessBeforeInitialization(Object bean, String beanName)
                  throws BeansException
    {
        return bean;
    }

    @Override
    public Object postProcessAfterInitialization(Object bean, String beanName)
                  throws BeansException
    {
        if(applicationContext.isSingleton(beanName)) {
            eventBus.register(bean);
        } else {
            if(containsSubscribe(bean)) {
                log.warn("Bean {} containing @Subscribe annotation(s) was not "
                    + "registered with EventBus. EventBus registration of "
                    + "prototype beans (isSingleton() == false) can cause "
                    + "memory leaks.", beanName);
            }
        }
        return bean;
    }

    @Autowired private ApplicationContext applicationContext;
    @Autowired private EventBus eventBus;
}

Using Guava EventBus with Spring

Recently, I started working on VeloxMUD again. The time away has really given me a new perspective on the code. Usually, that perspective goes like this:

• What the heck was I thinking?

The first thing I looked at was the code that handled connections for the MUD. There is a thread that waits on socket.accept() and then passes the Socket objects off to a handler service (injected by Spring). Although this isn't terrible, I thought I could improve it by using a Publish-Subscribe pattern to decouple the two.

I started my search with Observable and found that it wasn't going to fit. Although the Observer interface isn't bad, the need to derive from Observable wasn't going to work for me. My publisher (the "observable" object) already derived from Thread. And it seemed there had to be a better way.

I stumbled upon Guava's EventBus. Ah ha! This is what I need! But wait, where are all the publish-subscribe guts that I need to implement? Gone... Publishers post events of any arbitrary type, subscribers add a method (with any name) and a @Subscribe annotation. Done. Wow! This is observable done right!

Oops... one small problem. Most of the stuff that needs to register is created and managed by Spring. How do I register my subscribers without tackling all sorts of nasty lifecycle problems?

BeanPostProcessor comes to the rescue! We can provide custom bean-processing code to Spring. With the right piece of code, Spring can do all the necessary registration for us.

/*

 * EventBusPostProcessor.java

 * Author: Patrick Meade
 *
 * EventBusPostProcessor.java is hereby placed into the public domain.
 * Use it as you see fit, and entirely at your own risk.
 */

package com.example.spring.guava;

import com.google.common.eventbus.EventBus;

import com.google.common.eventbus.Subscribe;

import java.lang.annotation.Annotation;

import java.lang.reflect.Method;

import org.slf4j.Logger;

import org.slf4j.LoggerFactory;

import org.springframework.beans.BeansException;

import org.springframework.beans.factory.annotation.Autowired;

import org.springframework.beans.factory.config.BeanPostProcessor;

/**

 * EventBusPostProcessor registers Spring beans with EventBus. All beans

 * containing Guava's @Subscribe annotation are registered.

 * @author pmeade

 */

public class EventBusPostProcessor implements BeanPostProcessor

{

    private final Logger log = LoggerFactory.getLogger(this.getClass());

    

    @Override

    public Object postProcessBeforeInitialization(Object bean, String beanName)

            throws BeansException

    {

        return bean;

    }

    @Override

    public Object postProcessAfterInitialization(Object bean, String beanName)

            throws BeansException

    {

        // for each method in the bean

        Method[] methods = bean.getClass().getMethods();

        for(Method method : methods)

        {

            // check the annotations on that method

            Annotation[] annotations = method.getAnnotations();

            for(Annotation annotation : annotations)

            {

                // if it contains the Subscribe annotation

                if(annotation.annotationType().equals(Subscribe.class))

                {

                    // register it with the event bus

                    eventBus.register(bean);

                    log.trace("Bean {} containing method {} was subscribed to {}",

                        new Object[] {

                            beanName, method.getName(),

                            EventBus.class.getCanonicalName()

                        });
                    // we only need to register once
                    return bean;

                }

            }

        }

        

        return bean;

    }

    

    @Autowired

    private EventBus eventBus;

}

We add the following XML stanzas to Spring's application context:

<bean id="eventBus"
      class="com.google.common.eventbus.EventBus"/>

<bean id="eventBusPostProcessor"
      class="com.example.spring.guava.EventBusPostProcessor"/>

And it works! Spring registers every bean with a @Subscribe annotation.

2012-06-05 00:50:09,084 TRACE [main] com.example.spring.guava.EventBusPostProcessor (EventBusPostProcessor.java:64) - Bean connectionService containing method handleConnection was subscribed to com.google.common.eventbus.EventBus

S3E1: Node Equation Review

This is just a quick review of the node equation idea. In the following circuit there is one unknown node potential, labeled . The device parameters are: , , V, V.

What is the unknown potential (in Volts)? 6.21

e = ((e-V1) / R1) + ((e+V2) / R2)

[1/R1 + 1/R2] * e = (V1 / R1) - (V2 / R2)

[R2 / (R1*R2) + R1 / (R1*R2)] * e = (V1 / R1) - (V2 / R2)

[R2 / (R1*R2) + R1 / (R1*R2)] = (R2+R1) / (R1*R2) = 0.00032563

e = ((V1 / R1) / 0.00032563) - ((V2 / R2) / 0.00032563)

e = ((5.0 / 6800) / 0.00032563)  - ((-7.2 / 5600) / 0.00032563)

e = (0.000735294 / 0.00032563) - (-0.001285714 / 0.00032563)

e = 2.258065903 + 3.948389276 = 6.206455179

e = 6.21 Volts

VeloxMUD Mobile Authenticator

So I've been writing a MUD since Christmas Eve of 2011. Recently I took a two month break from the project to get some distance from the code, research some ideas in existing MUDs, etc.

This weekend I had a thought ... wouldn't it be neat if my MUD had a Mobile Authenticator similar to Blizzard's Battle.Net Mobile Authenticator?

So I wrote one: https://github.com/blinkdog/veloxmud-mobile-authenticator

The authentication code changes every 15 seconds...

Now I have to add the authentication routines to the MUD itself. I don't think that will be nearly as hard as futzing with the Android layout!

Android Virtual Device on 64-bit Linux

So I was trying to create a new Android Virtual Device (AVD) and it didn't work...

So I did a quick search and found an article on anddev.org:

All right, I was able to figure out the problem. The short of it is that I was using 64-bit Linux and had not installed the ia32-libs package, so the mksdcard utility was not working correctly. After installing this package, I was able to complete the step of making a virtual device.

So I took the advice and ran this:

sudo apt-get install ia32-libs

And then I was able to make my AVD.

Just a second...

So I wanted my desktop clock in GNOME 3 to display seconds. I did a quick search and found an article on AskUbuntu.com:

Yes, run this command in a Terminal: 

gsettings set org.gnome.shell.clock show-seconds true 

And you can verify with: 

gsettings get org.gnome.shell.clock show-seconds

And it worked like a charm. My desktop clock is now displaying seconds.