COMMAND

    Messenger/Hotmail

SYSTEMS AFFECTED

    Messenger/Hotmail

PROBLEM

    Gregory Duchemin found following.  The problem described below  is
    still  working  on  the   latest  MSN  client  version   currently
    available.  A  bug in the  Hotmail Messenger cryptographic  system
    may  allow  the  recovery  of  millions  of  hotmail   mailboxes's
    password.

    Microsoft MSN messenger is  a very handy little  win32 application
    designed  to  keep  in  touch  with friends, family, collaborators
    around the  world.   It offers  many nice  features like real time
    chats, hotmail mailbox access, etc...

    Messenger runs with its own  protocol to communicate with a  bunch
    of Microsoft  dedicated servers  and authenticate  itself with the
    same password than hotmail  is using (through the  global passport
    system).  The password is not sent clearly on the wire but  hashed
    with MD5 in the following manner.

    While negociating  a connection  with a  remote Microsoft  server,
    msn  clients  clearly   send  the  target   user  mailbox  to   be
    authenticated  with  (basically  the  username)  and  get  back  a
    scrambler string to be prepend  to the password before hashing  it
    and sending it.

        client ----- VER xx MSNP5 MSNP4 CVR0 --------------->  MSN server
        
        client <---- VER xx MSNP5 MSNP4 CVR0 ---------------   MSN server
        
        client ----- INF (xx+1) ---------------------------->  MSN server
        
        client <---- INF (xx+1) MD5 ------------------------   MSN server
        
        client ----- USR (xx+2) MD5 I ---------------------->  MSN server
        
        client <---- USR (xx+2) MD5 S yyyyyyyyy.yyyyyyyyy --   MSN server (the
        scrambler string is actually made with seconds.microseconds)

        client ----- USR (xx+3) MD5 S xxxxx...(32 chars) --->  MSN server

    Here it  is, the  password hash  has been  sent and  may be easily
    broken by bruteforcing it.

    The hash  creation process  is as  follow.   Say user  toto has  a
    password  "titan".    Then   his  client   generate  the    string
    "yyyyyyyyy.yyyyyyyyytitan"  and  the   according  MD5  hash,   say
    xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.        The      client      send
    MD5(yyyyyyyyy.yyyyyyyyytitan) on the wire.

    By sniffing the wire, a malicious user can obviously retrieve  the
    scrambler  string  and  the  final  hash.   Then  he  can  start a
    bruteforce session trying all password combinaisons with the  same
    scrambler prepended and comparing the resulting hash with this  he
    previously sniffed. (an exhaustive attack)

    Basically,  without  any  bug,  messenger  is  already  vulnerable
    because of the weak cryptographic scheme it uses.

    Gregory wrote, with the great help of Simeon Pilgrim, a very  fast
    MD5  bruteforcer  designed  to  use  scrambler  strings to finally
    retrieve an original password for a given MD5 hash.  Currently  it
    takes only 12 days to exhaust all 8 chars length passwords in  the
    charset [a-z0-9]  with an  average speed  of 2  600 000 hashes sec
    with only one 1 Ghz athlon processor. (we considere to be able  to
    test up to 4 000 000 hashes/sec with the next release and one  1.3
    Ghz processor).  Win32/Unix versions are freely available at

        http://mdcrack.multimania.com

    Another important point is that, if nowadays users can't  actually
    choose a  new password  lesser than  8 chars  length, all  old and
    weak passwords  (from 1  to 7  chars) are  still in  use and  just
    works perfectly with MSN.   How many users are currently  at risk?
    Too much!

    The last point  is a nasty  bug in the  client implementation that
    allow a malicious user, spoofing the MSN server, to send a  (NULL)
    scrambler string.  In such a case and intead of simply closing the
    connection, the client send  the mere password hash  making things
    even faster for a further bruteforce attack.

        client <---- USR (xx+2) MD5 S ----------------------   fake MSN server
        
        client ----- USR (xx+3) MD5 S xxxxx...(32 chars) --->  fake MSN server

    where xxxx...(32 chars) is actually MD5(password).

    Note that if this technic is still stealthy, it may need, in  some
    network  topologies,  the  use  of  icmp redirect/ arp spoofing to
    redirect  all  the  flow  to  the  attacker machine inside a given
    network.   But this  kind of  attacks are  well known  by networks
    crackers.

    Note that all communications between clients and servers are in  a
    clear form, and  by the way,  many other identity  robbery attacks
    remain available for instance, when our victim is asking messenger
    to open his  mailbox, the malicious  user may send  another URL to
    the client  like a  spoofing site  with a  false hotmail relogging
    page.

    Because hotmail and MSN  are using the same  authentication system
    called passport,  compromising users  MSN account  is finally  the
    same trick than compromising  hotmail users mailbox.   A malicious
    user with  a freshly  hacked MSN  password can  use it either with
    messenger or with www.hotmail.com

    Because a  tremendous number  of people  are using  these services
    without taking too much care about their password strongness,  the
    number of potential victims is really great.

    The attack described above can  be released from any place  in the
    path between  the victim  and MSN  servers or  simply in  the same
    network, this is the mere prerequisite.

    It  seems  that  the  main  problem  here  is  that the exhaustive
    keysearch attack  has been  shown to  be possible  for small  keys
    within a  reasonable length  of time  on cheap  hardware.  This is
    nothing terribly  new, everyone  has been  cracking passwords  and
    keys for  ages, and  will keep  on doing  so, the  advent of cheap
    high performance computers has just made it quicker and easier  to
    have a go at it yourself.

    This doesn't help things like MSN messenger which were built  with
    fairly  weak  authentication  schemes,  where  the strength of the
    scheme was never really seriously questioned.  Whoops.

SOLUTION

    Choose a  quite strong  password (at  least 9  chars length with a
    good charset) and  change it as  regularly as possible.   Finally,
    never never trust  hotmail and any  other web based  free accounts
    for you very own mails.

    The solutions seem a bit obvious:
    1. Increase the size of the keyspace and enforce those limits.
    2. Increase  the   entropy  within  the   keyspace  and    provide
       enforcement mechanisms
    3. Rotate keys over periods short enough that a exhaustive  attack
       is impractical with a given time with given resources.
    4. Wrap the authentication process up inside a tunnel using SSL

    There are however some fairly serious problems with all of these:
    1-2 Mean forcing users to pick longer and more complex  passwords.
        This probably means more  people will choose the  'remember my
        password' option when given to  them.  This is probably  not a
        good idea if the machine  that is doing the remembering  isn't
        terribly secure for reasons we shouldn't have to explain.

    3   is is just  plain old impractical for something like  Hotmail,
        with a userbase  of several million  people some of  whom only
        check their mail there once every couple of months.

    4.  Would  mean  redesigning  and  then  pushing  new  clients  to
        everyone  signed  up,  as  well  as extensively re-engineering
        the client.  Not easy,  and potentially costly.  This  is also
        the most likely fix as it  imposes a one time overhead on  the
        user to upgrade  their software.   This still doesn't  fix the
        remember  my  password  problem,  but  would  make people less
        likely to use it as they  could still use their old weak  easy
        to   remember   passwords   albeit   in   a  nominally  secure
        environment.