• Welcome to Valhalla Legends Archive.
 

Explain M1 ?

Started by iNsaNe, August 13, 2007, 02:04 PM

Previous topic - Next topic

iNsaNe

Client Password Proof (M1)

This value is sent to Battle.net to prove that you know your own password. Again, this differs from standard SRP. In this formula, commas (,) indicate concatenation:

M1 = SHA1(SHA1(g) xor SHA1(N), SHA1(Username), s, A, B, K)

Username and password are converted to UPPER CASE prior to hashing. This value is sent to the server in SID_AUTH_ACCOUNTLOGONPROOF




I'm confused about the xor part of M1, can someone please explain? Every time i go to log in i'm receiving the invalid password message, and I'm sure it's because im not understanding the xor part of this formula.

Hdx

Eah, it would be best if you showed some code and example cases.
But anyways, heres the general idea:
byte[] g = SHA1.digest(47);
byte[] n = SHA1.digest(" \x87\xc7\x23\x85\x65\xf6\x16\x12\xd9...");
byte[] i = new byte[20];
for(int x = 0; x<20; x++)
  i[x] = g[x] ^ n[x];

~Hdx

Proud host of the JBLS server www.JBLS.org.
JBLS.org Status:
JBLS/BNLS Server Status

Camel

Quote from: iNsaNe on August 13, 2007, 02:04 PMI'm confused about the xor part of M1, can someone please explain? Every time i go to log in i'm receiving the invalid password message, and I'm sure it's because im not understanding the xor part of this formula.
First, let's define XOR, exclusive or:

A Boolean operator that returns a value of TRUE only if just one of its operands is TRUE. In contrast, an inclusive OR operator returns a value of TRUE if either or both of its operands are TRUE.

So:
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

[IRRELEVANT]
Instead of thinking of it in this context, I think it's easier to think of it as the parity (read: "is the sum of the parts an odd number?") of all of the things being XORed. If I asked you what the answer to (1 ^ 0 ^ 0 ^ 1 ^ 0 ^ 1) was, you could spend 30 or so seconds doing each operation in your head, or you could just tell me if there are an odd number of ones in the expression. Algorithmically, the latter is much simpler, and always produces the same result.
[/IRRELEVANT]

As a bitwise operator, it works the same way, except the operation is done on each bit of the parts. A SHA1 hash is 160 bits wide, and therefore the operation is done on each of the 160 bits.

Since most processors are 32 bits, it's conventional (but far from necessary) to treat a 160bit SHA1 hash as 5 DWords. In Hdx's code above, he treats it as 20 bytes, which is also acceptable - and is probably the simplest solution in Java.

Hope this helps.

iago

If you need more info on formulas, check out the document I wrote forever ago, when we first reversed it: http://www.javaop.com/~ron/documents/SRP.html

It contains code snippits for every step, so it should be reasonably easy to follow.
This'll make an interesting test for broken AV:
QuoteX5O!P%@AP[4\PZX54(P^)7CC)7}$EICAR-STANDARD-ANTIVIRUS-TEST-FILE!$H+H*


Barabajagal

On this topic/line of inquiry... I'd like to ask if anyone has a BigNum system for a BASIC language...  I've written most of one, but it doesn't have exponents yet, and some stuff (like modulo) is extremely slow.

leax

#5
if ur in .NET say VB
u can actaully import the java class so essentiall u can access the BigInteger class (ref: vjslib.dll)
though u gota manually convert signed and unsigned byte arrays

also regarding  SHA1(g) XOR SHA1(N) in this case is pretty much a constant which you can also dig up from iago's NLS class in javaOP


*edit
result = New Byte() {108, 14, 151, 237, 10, 249, 107, 171, 177, 88, 137, 235, 139, 186, 37, 164, 240, 140, 1, 248}
Warcarft3 Custom Game Host Bot Development
http://www.codelain.com

Barabajagal

I refuse to use .NET languages. I'm writing my system in PowerBasic, and I have the following untested code for my class:
#Include "StandardSHA"

Sub MakeArray(Num() As Byte, Vals() As Byte)
Dim I As Integer
Dim J As Integer
    J = 0
    For I = &HFF - UBound(Vals) To &HFF
        Num(I) = Vals(J)
        J = J + 1
    Next I
End Sub

Function BigNum_Compare(NumA() As Byte, NumB() As Byte) As Byte
Dim I As Integer
Dim Dif As Byte
    For I = 0 To &HFF
        If NumA(I) > NumB(I) Then
            Function = 1
            Exit For
        ElseIf NumA(I) < NumB(I) Then
            Function = 2
            Exit For
        End If
    Next I
End Function

Sub BigNum_ToString(NumA() As Byte, Ret As String)
Dim strS As String
Dim I    As Integer
    For I = 0 To UBound(NumA)
        strS = strS & Chr$(NumA(I))
    Next I
    Ret = strS
End Sub

Sub BigNum_FromString(NumA As String, Ret() As Byte)
Dim I    As Integer
    For I = UBound(Ret()) - Len(NumA) To UBound(Ret())
        Ret(I) = Asc(Mid$(NumA, I - (UBound(Ret()) - Len(NumA)), 1))
    Next I
End Sub

Sub AddVal(Num() As Byte, ByVal AddLoc As Long, ByVal ToAdd As Byte, RetNum() As Byte)
    If Num(AddLoc) + ToAdd > &HFF Then
        AddVal(Num(), AddLoc - 1, 1, Num())
        RetNum(AddLoc) = (Num(AddLoc) + ToAdd) - &H100
    Else
        RetNum(AddLoc) = Num(AddLoc) + ToAdd
    End If
End Sub

Sub SubVal(Num() As Byte, ByVal SubLoc As Long, ByVal ToSub As Byte, RetNum() As Byte)
    If Num(SubLoc) - ToSub < &H0 Then
        SubVal(Num(), SubLoc - 1, 1, Num())
        RetNum(SubLoc) = (Num(SubLoc) - ToSub) + &H100
    Else
        RetNum(SubLoc) = Num(SubLoc) - ToSub
    End If
End Sub

Sub BigNum_Add(NumA() As Byte, NumB() As Byte, Ret() As Byte)
Dim I As Integer
    For I = UBound(NumA) To 0 Step -1
        AddVal NumA(), I, NumB(I), Ret()
    Next I
End Sub

Sub BigNum_Subtract(NumA() As Byte, NumB() As Byte, Ret() As Byte)
Dim I As Integer
    For I = UBound(NumA) To 0 Step -1
        SubVal NumA(), I, NumB(I), Ret()
    Next I
End Sub

Sub BigNum_Multiply(NumA() As Byte, NumB() As Byte, Ret() As Byte)
Dim I As Integer
Dim J As Integer
Dim rVal             As Integer
Dim rCarry           As Byte
Dim rLast            As Byte
Dim tRet(&HFF)       As Byte
Dim uRet(&HFF)       As Byte
Dim fRet(&HFF, &HFF) As Byte
    For I = UBound(NumB) To 0 Step -1
        For J = UBound(NumA) To 0 Step -1
            RVal = NumA(J) * NumB(I) + RLast
            RCarry = 0
            If RVal > &HFF Then
                RCarry = RVal \ 256
                RVal = RVal Mod 256
            End If
            fRet(I, J) = RVal
            rLast = rCarry
        Next J
    Next I
    For I = &HFF To 0 Step - 1
        For J = 0 To &HFF
            tRet(J) = fRet(I, J)
        Next J
        BigNum_Add Ret(), tRet(), uRet()
        For J = 0 To &HFF
            Ret(J) = uRet(J)
        Next J
    Next I
End Sub

Sub BigNum_Modulo(NumA() As Byte, NumB() As Byte, Ret() As Byte)
Dim I          As Integer
    Do While BigNum_Compare(NumA(), NumB()) = 1
        BigNum_Subtract NumA(), NumB(), NumA()
    Loop
    For I = 0 To &HFF
        Ret(I) = NumA(I)
    Next I
End Sub

Sub BigNum_Hash(NumA() As Byte, Ret() As Byte)
Dim strToHash As String
Dim strHash   As String
    BigNum_ToString NumA(), strToHash
    strHash = StandardSHA1(strToHash)
    BigNum_FromString strHash, Ret()
End Sub

It's not very well made, I know, but I don't know this language's capabilities very well yet, and I really don't know how the hell bignum stuff should work in the least.

iNsaNe

Sorry guys this is a somewhat old topic I just came back to my bot so far in C# and I'm still getting an invalid password response. I feel stupid asking for help what's wrong with the M1 code I have because I've been looking at iago's and myndfyre's codes for a while now. But I'm getting an invalid password response every time..

I'll post the full log, but if you need the code (I'm not going to consider it fully mine) I'll post it.

Connecting with WAR3 ...
.

C -> S 0x50:
                     ff 50 3a 00 00 00 00 00 36         .P:.....6
38 58 49 33 52 41 57 15 00 00 00 00 00 00 00 00  8XI3RAW.........
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 55  ...............U
53 41 00 55 6e 69 74 65 64 20 53 74 61 74 65 73  SA.United States
00                                               .

S -> C 0x25:

                        ff 25 08 00 83 be 71 73  .......%....qs

S -> C 0x50:

                  ff 50 e6 00 02 00 00 00 dc 85  ..2....P........
3b 83 5f 3f 1c 00 00 4d 89 7e 99 cb c6 01 76 65  ;._?...M.~....ve
72 2d 49 58 38 36 2d 34 2e 6d 70 71 00 43 3d 33  r-IX86-4.mpq.C=3
30 33 39 35 32 35 31 38 34 20 41 3d 31 39 39 36  039525184 A=1996
30 35 35 34 38 32 20 42 3d 34 30 36 32 38 35 38  055482 B=4062858
34 20 34 20 41 3d 41 5e 53 20 42 3d 42 5e 43 20  4 4 A=A^S B=B^C
43 3d 43 2d 41 20 41 3d 41 5e 42 00 f7 f9 67 a6  C=C-A A=A^B...g.
a0 93 85 48 39 58 b6 61 98 de 6d df ee 9b 1d 39  ...H9X.a..m....9
b8 57 69 87 cf 36 ae ef 43 e2 f8 f4 19 0a 6a 1b  .Wi..6..C.....j.
0a f0 f7 03 3f d6 ea 75 9b 93 0a 31 ea ad 4f 13  ....?..u...1..O.
d5 4e a8 6c c2 1b df 8a c9 bf 88 d7 26 ae 0f 3d  .N.l........&..=
9b 77 a7 04 44 42 41 c1 be 5b d2 fe 73 93 f0 6c  .w..DBA..[..s..l
0f 60 5a 43 62 58 fa 41 f2 d5 b4 9b 4c 43 ec 94  .`ZCbX.A....LC..
74 7c d8 06 de de a5 76 fe f3 8b 19 e5 2d cb fb  t|.....v.....-..
b1 f7 1d 74 b9 31 26 3d 43 2d 02 2b              ...t.1&=C-.+

C -> S 0x51:

                  ff 51 63 00 e7 eb e4 02 15 00  ..t....Qc.......
01 00 28 97 71 79 01 00 00 00 00 00 00 00 1a 00  ..(.qy..........
00 00 0e 00 00 00 0a 66 70 00 00 00 00 00 d8 7f  .......fp.......
6e e7 68 c1 41 e5 a8 17 49 34 99 d5 9a 6b 2d 9f  n.h.A...I4...k-.
68 00 77 61 72 33 2e 65 78 65 20 31 32 2f 32 38  h.war3.exe 12/28
2f 30 36 20 33 30 3a 33 35 3a 32 31 20 31 35 37  /06 30:35:21 157
32 33 30 37 00 34 32 32 00                       2307.422.

(422 is my account name which is the cd key owner name :P dont be confused)

S -> C 0x51:

                     ff 51 09 00 00 00 00 00 00  .a.....Q.......

C -> S 0x53:

                  ff 53 28 00 72 c0 76 88 d5 31  ..#....S(.r.v..1
2d 42 18 48 55 c9 a7 ea 20 ea fd 81 1f 22 ce 8a  -B.HU... ...."..
f9 4f c2 7b d8 03 78 64 10 a1 34 32 32 00        .O.{..xd..422.

(422 is my account name again)

S -> C 0x53:

                  ff 53 48 00 00 00 00 00 88 db  [email protected].......
2c 8a a2 57 ff 16 fa 03 79 df b0 00 4c be 95 4a  ,..W....y...L..J
7f 4c d2 23 63 85 0f e9 ff 27 7f a7 2c a2 42 88  .L.#c....'..,.B.
01 01 f9 c8 58 d7 da af 19 17 35 2a a8 4d 67 60  ....X.....5*.Mg`
b0 7f c8 07 96 58 9a fd 0a 35 85 f8 e4 28        .....X...5...(

C -> S 0x54:

                  ff 54 18 00 79 71 59 49 7c 4a  ...j...T..yqYI|J
23 4c 3d 37 a5 27 16 a4 9e 45 49 db 6c d0        #L=7.'...EI.l.

S -> C 0x54:

                  ff 54 1c 00 02 00 00 00 00 00  .!.2...T........
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00 00                                            ..


02 00 00 00 of death -.-
any help?

Hdx

From what you posted, I would have to say you entered the wrong password. As I would assume your SRP class is perfect. As you deemed it unnessasary to post.
AE: Post your code -.-
And don't bump old ass threads.
~Hdx

Proud host of the JBLS server www.JBLS.org.
JBLS.org Status:
JBLS/BNLS Server Status

iNsaNe

#9

using System;
using System.Collections.Generic;
using System.Text;
namespace Infinite_Bot_v1
{
    class NLS
    {
        bool INIT = false;
        string Username;
        string Password;
        BigInteger g = new BigInteger("47", 10);
        BigInteger N = new BigInteger("112624315653284427036559548610503669920632123929604336254260115573677366691719", 10);
        BigInteger B;
        BigInteger A;
        BigInteger a;
        BigInteger S;
        BigInteger u;
        BigInteger x;
        BigInteger v;
        byte[] Salt;
        byte[] ServerKey;
        byte[] K;
        bool CLIENTKEYUSED = false;
        bool VERIFIERUSED = false;
        bool USERNAMEPWHASHUSED = false;
        System.Security.Cryptography.SHA1 Sha = new System.Security.Cryptography.SHA1Managed();
        System.Security.Cryptography.RandomNumberGenerator RNGen = new System.Security.Cryptography.RNGCryptoServiceProvider();
        private void CHECKINIT()
        {
            if (!INIT)
                throw new Exception("NLS has not been initialized.");
        }
        private byte[] GetUsernamePWHash(byte[] salt)
        {
            if (USERNAMEPWHASHUSED)
                return x.getBytes();
            USERNAMEPWHASHUSED = true;
            byte[] AccPw = System.Text.Encoding.ASCII.GetBytes(Username.ToUpper() + ":" + Password.ToUpper());
            byte[] hashAccPw = Sha.ComputeHash(AccPw);
            byte[] salt_and_hashAccPw = new byte[52];
            Array.Copy(salt, 0, salt_and_hashAccPw, 0, 32);
            Array.Copy(hashAccPw, 0, salt_and_hashAccPw, 32, 20);
            byte[] vData = Sha.ComputeHash(salt_and_hashAccPw);
            x = new BigInteger(vData);
            return x.getBytes();
        }
        public NLS()
        {
        }
        public NLS(string username, string password)
        {
            if (INIT)
                throw new Exception("NLS has already been initialized.");
            INIT = true;
            Username = username;
            Password = password;
        }
        public byte[] GetClientKey()
        {
            if (CLIENTKEYUSED)
                return A.getBytes();
            CLIENTKEYUSED = true;
            byte[] NonZeroBytes = new byte[32];
            RNGen.GetNonZeroBytes(NonZeroBytes);
            a = new BigInteger(NonZeroBytes);
            a %= N;
            A = g.modPow(a, N);
            return A.getBytes();
        }
        public byte[] GetVerifier(byte[] salt)
        {
            if (VERIFIERUSED)
                return v.getBytes();
            VERIFIERUSED = true;
            if (USERNAMEPWHASHUSED)
            {
                v = new BigInteger(g.modPow(x, N));
                return v.getBytes();
            }
            else
            {
                BigInteger bi_x = new BigInteger(GetUsernamePWHash(salt));
                v = new BigInteger(g.modPow(bi_x, N));
                return v.getBytes();
            }
        }
        public byte[] CreateSalt()
        {
            Salt = new byte[32];
            RNGen.GetNonZeroBytes(Salt);
            return Salt;
        }
        public byte[] GetM1(byte[] salt, byte[] serverkey)
        {
            if (salt.Length != 32)
                throw new Exception("Salt index out of bounds.");
            if (serverkey.Length != 32)
                throw new Exception("Server Key index out of bounds.");
            if (!CLIENTKEYUSED)
                throw new Exception("You must generate a Client Key before accessing this function.");
            Salt = salt;
            ServerKey = serverkey;
            B = new BigInteger(serverkey);
            //B
            if (!USERNAMEPWHASHUSED)
                GetUsernamePWHash(salt);
            //x
            if (!VERIFIERUSED)
                GetVerifier(salt);
            BigInteger g_XoR_N = new BigInteger("1415864289515498529999010855430909456942718455404", 10);
            //Sha1(g) xor Sha1(N)
            byte[] Acc = System.Text.Encoding.ASCII.GetBytes(Username.ToUpper());
            byte[] hashAcc = Sha.ComputeHash(Acc);
            //Username hash
            byte[] hashB = Sha.ComputeHash(serverkey);
            byte[] uBytes = new byte[4];
            for (int i = 0; i <= 3; i++)
                uBytes[i] = hashB[3 - i];
            u = new BigInteger(uBytes);
            //u
            S = new BigInteger(((N + B) - v) % N);
            S = S.modPow(a + (u * x), N);
            //S
            K = new byte[40];
            byte[] SBytes = S.getBytes();
            byte[] EvensIN = new byte[SBytes.Length / 2];
            byte[] OddsIN = new byte[SBytes.Length / 2];
            for (int i = 0; i < EvensIN.Length; i++)
            {
                EvensIN[i] = SBytes[i * 2];
                OddsIN[i] = SBytes[(i * 2) + 1];
            }
            byte[] EvensOUT = Sha.ComputeHash(EvensIN);
            byte[] OddsOUT = Sha.ComputeHash(OddsIN);
            for (int i = 0; i < EvensOUT.Length; i++)
            {
                K[i * 2] = EvensOUT[i];
                K[(i * 2) + 1] = OddsOUT[i];
            }
            //K
            System.IO.MemoryStream memStream = new System.IO.MemoryStream();
            System.IO.BinaryWriter BW = new System.IO.BinaryWriter(memStream);
            BW.Write(g_XoR_N.getBytes());
            BW.Write(hashAcc);
            BW.Write(salt);
            BW.Write(A.getBytes());
            BW.Write(serverkey);
            BW.Write(K);
            BW.Close();
            byte[] M1 = Sha.ComputeHash(memStream.GetBuffer());
            memStream.Close();
            return M1;
        }
    }
}


That's the whole class. You'll see a lot of code from iago and myndfyre so I'd like to thank them for all the help they do for valhallalegends and/or other communities.