As the title suggests this is a quick guide to the authentication mechanism DIGEST-MD5 as used in XMPP. Digest authentication is used in other protocols also, but they are outside of the scope of this article.

Once an XMPP stream has been established and the DIGEST-MD5 SASL mechanism selected, the host should respond with a challenge that looks something like (when decoded from base-64):

realm="zoofware.com",nonce="0ddba11",qop="auth",charset=utf-8,algorithm=md5-sess

Now, the correct response would be:

username="jwb",realm="zoofware.com",nonce="0ddba11",cnonce="39931f36af066660f551
6142cbf02767",nc=00000001,qop=auth,digest-uri="xmpp/zoofware.com",charset=utf-8,
response=3353792a75fcb3337560e2a33041b3fa

Creating most of the response is incredibly simple, it’s simply a string composed of the following attributes:

  • username – The username part of the user’s JID (i.e jwb@zoofware.com)
  • realm – This should be the same realm as sent in the challenge, which should be the same as the domain part of the user’s JID.
  • nonce – Essentially an arbitrary string which is sent by the server in the challenge. It is for security.
  • cnonce – Another string, but this time generated by the client. It doesn’t matter what it is. Again for security.
  • nc – An incrementing counter to identify each request. Generally there is no need to change this from “00000001″.
  • qop – For XMPP, this will always be “auth”.
  • digest-uri – Simply the realm appended to the string “xmpp/”.
  • charset – The encoding to use.
  • The “response” directive is the hardest to generate; it is a hash based on several other hashes of passwords and so on and can be done in several steps. I have included my specific client C# code in the example.

    The following example uses the following directives:

    realm=”zoofware.com”
    username=”jwb”
    nonce=”0ddba11″
    password=”secret”
    cnonce=”randomz”
    digest-uri=”xmpp/zoofware.com”

    Step 1

    Create a string of the form "username:realm:password".
    Save this string as a byte array called A1.

    byte[] A1 = ASCIIEncoding.UTF8.GetBytes(string.Format("{0}:{1}:{2}", Xmpp.UserName, Xmpp.UserDomain, Xmpp.Password));

    Now compute the MD5 hash of A1 and keep the result in a byte array HA1_1.

    MD5 md5 = MD5.Create();
    byte[] HA1_1 = md5.ComputeHash(A1);

    .

    The result so far should be HA1_1 = afaab39bafa10040c5d165030c03e278.

    Step 2

    Create a string of the form ":nonce:cnonce" and save it as a byte array HA1_2.

    byte[] HA1_2 = ASCIIEncoding.UTF8.GetBytes(string.Format(":{0}:{1}", elements["nonce"], cnonce));

    .

    Create a byte array HA1 which has a length equal to the length of HA1_1 + HA1_2. Then copy the cotents of HA1_1 and HA1_2 into the new array.

    byte[] HA1 = new byte[HA1_2.Length + HA1_1.Length];
    HA1_1.CopyTo(HA1, 0);
    HA1_2.CopyTo(HA1, HA1_1.Length);

    Compute the MD5 of HA1 and call it HA1.

    HA1 = md5.ComputeHash(HA1);

    .

    The result so far should be HA1 = ef92f7f90f8bd0a364f01cfe9e9b0564.

    Step 3

    Create a byte array HA2 with the contents of the MD5 hash of the string “AUTHENTICATE:digest-uri”.

    byte[] HA2 = md5.ComputeHash(ASCIIEncoding.UTF8.GetBytes(string.Format("AUTHENTICATE:xmpp/{0}", Xmpp.UserDomain)));

    HA2 = c51d568aff0c3f543bdfbba2a6010a75.

    Step 4

    Now create two strings sHA1 and sHA2. Their contents need to be the base 16 representation of HA1 and HA2.

    Important: Do not just convert each byte to it’s ASCII letter. The string needs to be its literal value.

    For example, the byte array { 0x1a, 0x2e, 0x3f } would become the string 1a2e3f.

    public static string ConvertToHexString(byte[] inArray)
    {
         StringBuilder sb = new StringBuilder();
    
         foreach (byte part in inArray)
         {
             sb.AppendFormat("{0:x2}", part);
         }
    
         return sb.ToString();
    }

    Then compute the MD5 hash of the string “sHA1:nonce:nc:cnonce:qop:sHA2″. Save the result as the byte array hash.

    So far: hash = 6dd79d3dee313216e188bfc17b6254b5.

    byte[] b = ASCIIEncoding.ASCII.GetBytes(string.Format("{0}:{1}:{2}:{3}:{4}:{5}", ConvertToHexString(HA1), elements["nonce"], "00000001", cnonce, elements["qop"], ConvertToHexString(HA2)));
    
    byte[] hash = md5.ComputeHash(b);

    Final Step

    pheww!

    The base 16 representation of hash can now be used as the value for the response directive.

    Thus the final response will be:

    username="jwb",realm="zoofware.com",nonce="0ddba11",cnonce="randomz",nc=00000001
    ,qop=auth,digest-uri="xmpp/zoofware.com",charset=utf-8,response=6dd79d3dee313216
    e188bfc17b6254b5
    .

    Note: I’m not experienced with DIGEST-MD5 at all, so this solution my be incomplete for some situations. It does however work with the XMPP hosts I’ve tried it with.

    Further reading:

  • http://en.wikipedia.org/wiki/Digest_access_authentication
  • http://www.ietf.org/rfc/rfc2831.txt
  • http://web.archive.org/web/20050224191820/http://cataclysm.cx/wip/digest-md5-crash.html
  • http://www.charliedigital.com/CategoryView,category,XMPP.aspx
  • Over the weekend I’ve been busy writing an XMPP client from scratch. So far, I’ve got a basic console application connected to Facebook chat. No sending messages support yet, but the friends list, receiving messages and presence data are working quite well.

    Its also connected successfully to Google Chat or Talk or whatever it’s called using TSL.

    By far the hardest thing to implement was the digest authentication (DIGEST-MD5) mechanism used by Facebook (and many other hosts, Google supports PLAIN). The C# code for creating the response hash looks something like this:

    MD5 md5 = MD5.Create();
    
    byte[] a = ASCIIEncoding.ASCII.GetBytes(string.Format("{0}:{1}:{2}", Xmpp.UserName, Xmpp.UserDomain, Xmpp.Password));
    byte[] HA1_1 = md5.ComputeHash(a);
    byte[] HA1_2 = ASCIIEncoding.ASCII.GetBytes(string.Format(":{0}:{1}", elements["nonce"], cnonce));
    byte[] HA1 = new byte[HA1_2.Length + HA1_1.Length];
    
    HA1_1.CopyTo(HA1, 0);
    HA1_2.CopyTo(HA1, HA1_1.Length);
    
    HA1 = md5.ComputeHash(HA1);
    
    byte[] HA2 = Md5.ComputeHash(ASCIIEncoding.ASCII.GetBytes(string.Format("AUTHENTICATE:xmpp/{0}",xmpp.UserDomain)));
    
    byte[] b = ASCIIEncoding.ASCII.GetBytes(string.Format("{0}:{1}:{2}:{3}:{4}:{5}", ConvertToHexString(HA1), elements["nonce"], "00000001", cnonce, elements["qop"], ConvertToHexString(HA2)));
    
    byte[] hash = md5.ComputeHash(b);
    string res = ConvertToHexString(hash);

    And the code to convert an array of bytes to a base 16 string:

    public static string ConvertToHexString(byte[] inArray)
    {
    	StringBuilder sb = new StringBuilder();
    	foreach (byte part in inArray)
            {
            	sb.AppendFormat("{0:x2}", part);
            }
    
            return sb.ToString();
    }

    In the next few days I’ll write up a brief DIGEST-MD5 tutorial as I wasted quite a bit of time trying to piece it together from various resources and RFCs.

    Well, University is closing to an end in the next week or two, so I’ll finally have a little time for my own projects.

    It seems that I always grow bored of unfinished projects and move on to something new. My main aims over the summer (geek-wise) are to create a .NET XMPP client (specifically tailored towards Facebook chat, I hate having to have a browser window open all the time!) and porting the Z80/SMS emulator to C++.

    Finishing the emulator probably isn’t such a great priority and most likely will never be completed; it is however a great opportunity to learn C++ and branch out from .NET a little.

    Not forgetting the Matrix calculator I’d like to extend with cofactors, determinants and minors. And, of course, an F# algebra evaluator would be a great thing to add support for.

    I may also get involved with an Open Source project, mainly for the experience, and again would be a great for learning.

    I’ve been working on a little side project today which I’ve been thinking of doing for quite a while. It’s my intention to one day be able to write my own compiler for a custom designed language and so I have decided to start with something a little simpler: an algebraic equation evaluator.

    I’ve also chosen F# to write it in, learning which has been on my to-do list for quite awhile now, so most of the last few hours has been spent mostly getting to grips with its syntax, a world away from C-style braces, and the functional way of doing things.

    A basic parser is now working and the next step will be figuring out how to produce an expression tree, evaluate the nodes and return the result (either as a string or as some sort of expression object).

    F# includes some neat stuff for this exact kind of situation, for example, a basic expression evaluator:

    type expr =
        | Binary of string * expr * expr
        | Constant of float
    
    let v = Binary("+", Constant 2.0, Binary("+", Constant(2.0), Constant(2.0)))
    
    let rec eval v =
        match v with
        | Binary(op, lhs, rhs) ->
            match op with
            | "+" -> eval(lhs) + eval(rhs)
        | Constant(n) ->
            n       

    (thanks to http://msdn.microsoft.com/en-us/magazine/cc164244.aspx#S6 for that ;) )

    Essentially all that code does is define two types of expressions, one which consists of a binary operator with two operands (which are also expressions) and one that is simply a constant value.

    The recursive evaluation function then iterates over the parent expression, its children and its children’s children etc. ad infinitum and evaluates them all. In theory every

    expr

    object will eventually evaluate down to a constant.

    I whipped out Expression Blend today and gave the matrix calculator a bit of a tidy up. It now supports transposition and calculating the determinant of 2×2 matrices (and once I’ve figured out Leibniz’s or Laplace’s determinant formulae I’ll support arbitrary dimensions as well as finding the inverse).

    http://zoofware.com/zoofware-matrix-machine/

    Hi all, over the last two days I’ve developed a Silverlight matrix calculator which can add and multiply matrices of arbitrary sizes. I’m not 100% sure it has no bugs, so beware if you’re using it to cheat on your homework! :P

    Zoofware Matrix Machine: http://zoofware.com/zoofware-matrix-machine/

    It’s the only bit of coding I’ve done over the last few weeks :( However, I haven’t forgotten about the emulator. Once summer is upon us I’ll get cracking, but in the meantime I’m going to work on smaller maths related programs which don’t require as much time or effort to make and supplement my University course nicely. ;)

    Having started back at University, I’ve been drowned like a rat in a pile of Maths and haven’t had much time to work on the emulator.

    However, I have been advised to build a built in stepping debugger which will make fixing bugs a lot easier (as well as being a less time consuming part of the project), so this will be my main focus for the next couple of weeks. My GUI skills could do with brushing up anyway, so It’ll be a worthwhile development.

    I might also try and get a working Silverlight prototype running Sonic 1, just to explore the possible rendering methods (Silverlight doesn’t allow pointers, which will make bitmap manipulation very slow).

    Update 12/02/2010: Between having a social life (yeh, I’m not that much of a geek ;) ) and Uni, I’ve literally had no time at all to continue with the project. I can’t see any major work being done until mid-May. Time away from coding though has given me a lot of new ideas for future development.

    Following over a week of trying to understand the horizontal and vertical scrolling of the VDP, implementing background priorities and masking, as well as re-writing most of the VDP emulator to be severely cleaner, it is now possible to play Sonic 1 nearly perfectly from start to finish (well up to the 4th zone anyway, then I get bored, I’m not much of a gamer :P ). I suspect there might be a problem with the score counter which wraps after 4 digits, though I’ve not yet had chance to confirm its proper behaviour. There’s also the occasional slowdown, nothing overly serious.

    I’ve also managed to track down a bug (I think / hope) which was causing quite a few commercial ROMs and several homebrews to produce garbled background tiles. There seems to be nothing going amiss in the VDP and a common factor of the ROMs with this problem appears to be the use of the RETI and RETN Z80 opcodes. Hopefully this will be fixed up soon.

    The next stage of development will be starting work on the sound emulation, as well as possibly coming up with a better GUI.

    Update 20/01/10: The Sonic score wrapping was because of a bad flag being set in DAA and is now fixed.

    Update 21/01/10: The problem with garbled background tiles with one homebrew game was due to the VDP registers being set to 0 by default. They are now set to FFh. However, similar problems with several commercial games still elude me.

    1234

    After a lot of bug fixing; I have managed to get ZEXALL passing every opcode bar three (one of which is undocumented). ZEXALL isn’t exhaustive despite it’s own claims, so there’s bound to be many more bugs, but its a step in the right direction.

    Sonic now also loads properly, rings can be collected and enemies killed but only to a very limited extent due to horizontal scrolling not being implemented yet.

    In the next week or so I’m going to focus on get the VDP working right, along with sprite caching to speed it up a bit (profiling has shown that a huge amount of CPU time is being wasted in VDP.Render() / DrawPattern()).

    sonic_vs_zexall

    Basic sprites are now working correctly, zexall completes (though of course, with lots of errors ;) which I suspect might be down to a bad halfcarry method). I’ve also implemented rudimentary input.

    291209_2291209_1291209