Jump to content
Sign in to follow this  
Followers 0
Pike R. Alpha

Let's make random-seed really random

14 posts in this topic

Recommended Posts

Yosemite is around the corner, so I like to make the following proposal:

 

Let's make "random-seed" (a security related property) in Chameleon really random instead of using static values.

 

Note: C converted from disassembled code from Apple boot.efi 

    UInt8 index = 0;
    EFI_UINT16 PMTimerValue = 0;
    EFI_UINT32 randomValue, tempValue, cpuTick;
    EFI_UINT32 ecx, esi, edi = 0;
    EFI_UINT32 rcx, rdx, rsi, rdi;

    randomValue = tempValue = ecx = esi = edi = 0;
    rcx = rdx = rsi = rdi = cpuTick = 0;

    do_cpuid(0x00000001, p->CPU.CPUID[CPUID_1]); // Feature Information (Function 01h).

    if (p->CPU.CPUID[CPUID_1][0] & 0x40000000) // Checking ECX bit-30
    {
        //
        // For i5/i7 Ivy Bridge and Haswell Processors.
        //
        EFI_UINT32 seedBuffer[16] = {0};
        //
        // Main loop to get 16 qwords (four bytes each).
        //
        for (index = 0; index < 16; index++)
        {
             randomValue = computeRand();
             cpuTick = getCPUTick();
             randomValue = (randomValue ^ cpuTick);
             seedBuffer[index] = randomValue;
        }

        DT__AddProperty(chosenNode, "random-seed", sizeof(seedBuffer), (EFI_UINT32*) &seedBuffer);
    }
    else
    {
        //
        // For all other processors.
        //
        EFI_UINT8 seedBuffer[64] = {0};
        //
        // Main loop to get 64 bytes.
        //
        do
        {
            PMTimerValue = inw(0x408);
            esi = PMTimerValue;

            if (esi < ecx)
            {
                continue;
            }

            cpuTick = getCPUTick();
            rcx = (cpuTick >> 8);
            rdx = (cpuTick >> 10);
            rdi = rsi;
            rdi = (rdi ^ cpuTick);
            rdi = (rdi ^ rcx);
            rdi = (rdi ^ rdx);

            seedBuffer[index] = (rdi & 0xff);

            edi = (edi & 0x2f);
            edi = (edi + esi);
            index++;
            ecx = (edi & 0xffff);

        } while (index < 64);

        DT__AddProperty(chosenNode, "random-seed", sizeof(seedBuffer), (EFI_UINT8*) &seedBuffer);
}

In asm.s I added:

//
// computeRand()
//
LABEL(_computeRand)
  pushl %edx
  mov $0xa, %edx

Repeat:
  rdrand %eax
  jae Ok
  jmp Exit

Ok:
  dec %edx
  pause
  jne Repeat
  mov $0x0, %eax

Exit:
  popl %edx

ret

This is the getCPUTick() helper function I use:

EFI_UINT32 getCPUTick(void)
{
  uint32_t value = 0;

  __asm__ volatile("rdtsc" : "=A" (value));

  return value;
}

I have cleaned the code. Made it more Chameleon compatible (I hope) but I don't know what ECX is in Chameleon so please verify/change the bit-30 check!

Share this post


Link to post
Share on other sites

Oh, geeze...the subject of genuinely random numbers has been exhaustively studied in computer science for years, and the executive summary is that there is no such thing unless the source is naturally random noise.

 

Approaches to achieve random noise input include such interesting creations as sampled radio noise from multiple frequencies, sampling maps of the cosmic background radiation survey, psuedo Brownian motion observation using confetti in a wind tunnel from live video and a great deal of external input sampling. There are online sampler services (I have no links at the moment).

 

The counterpart is a simple, proven (with some difficulty) fact that unless the sample is taken from the real world, it isn't likely going to be really random.

 

Many PhD's have been earned on the subject. It can take a year to wade through the current state of knowledge.

 

There are, however, a wide range of well established algorithms you can find which enhance the appearance of randomness to acceptable levels, such that repetition or any form of predictability requires more memory and processing power than is available - a definition of acceptable that doesn't actually fit a scientifically or logically provable, real randomness, but effectively results in a practicably similar result.

Share this post


Link to post
Share on other sites

My PhD's are telling me that anything is better than a fixed non-random chosen mixture of bytes that I have used when I wrote the lines for Chameleon. Especially the code used by Apple self. But hey. Some people just like to argue everything to death. Like that is going to help.

Share this post


Link to post
Share on other sites

Oh, geeze...the subject of genuinely random numbers has been exhaustively studied in computer science for years, and the executive summary is that there is no such thing unless the source is naturally random noise.

 

Approaches to achieve random noise input include such interesting creations as sampled radio noise from multiple frequencies, sampling maps of the cosmic background radiation survey, psuedo Brownian motion observation using confetti in a wind tunnel from live video and a great deal of external input sampling. There are online sampler services (I have no links at the moment).

 

The counterpart is a simple, proven (with some difficulty) fact that unless the sample is taken from the real world, it isn't likely going to be really random.

 

Many PhD's have been earned on the subject. It can take a year to wade through the current state of knowledge.

 

There are, however, a wide range of well established algorithms you can find which enhance the appearance of randomness to acceptable levels, such that repetition or any form of predictability requires more memory and processing power than is available - a definition of acceptable that doesn't actually fit a scientifically or logically provable, real randomness, but effectively results in a practicably similar result.

Don't mix "real random" and "different on each boot". Say hello to your PhD from me.

Share this post


Link to post
Share on other sites

This is the getCPUTick() helper function I use:

EFI_UINT32 getCPUTick(void)
{
  uint32_t value = 0;

  __asm__ volatile("rdtsc" : "=A" (value));

  return value;
} 

 

What about this? (cpu.h)

static inline uint64_t getCPUTick(void)
{
    uint32_t lowest;
    uint32_t highest;
    __asm__ volatile ("rdtsc" : "=a" (lowest), "=d" (highest));
    return (uint64_t) highest << 32 | lowest;
}

 

ErmaC

Share this post


Link to post
Share on other sites

What is the value you get when you use something like: 

printf("value: 0x%lld\n", getCPUTick());

 

The values are:

value: 0x-134804764
value: 0x409574740
value: 0x947910944
value: 0x1491867824
value: 0x2035994796
value: 0x-1714696948
value: 0x-1170417844
value: 0x-631646100
value: 0x-87300420
value: 0x456880132
value: 0x1000907356
value: 0x1539243648
value: 0x2083210592
value: 0x-1667564396
value: 0x-1123216172
value: 0x-578805864
value: 0x-40042296
value: 0x504011696
value: 0x1048304480
value: 0x1592678976
value: 0x2137000888
value: 0x-1619331128
value: 0x-1074950712
value: 0x-530828592
value: 0x13134612
value: 0x557113308
value: 0x1095524960
value: 0x1639373640
value: 0x-2111634132
value: 0x-1567459544
value: 0x-1023107156
value: 0x-484922344
value: 0x58876712
value: 0x602943700
value: 0x1147123680
value: 0x1691113200
value: 0x-2065151500
value: 0x-1521113400
value: 0x-977139080
value: 0x-433166644
value: 0x110807716
value: 0x649212680
value: 0x1193465700
value: 0x1737653012
value: 0x-2013221460
value: 0x-1474582628
value: 0x-930753060
value: 0x-386564128
value: 0x157634572
value: 0x701746512
value: 0x1240516644
value: 0x1784913844
value: 0x-1965696784
value: 0x-1421477708
value: 0x-877380128
value: 0x-338609604
value: 0x205468956
value: 0x749470788
value: 0x1293564968
value: 0x1837866860
value: 0x-1918675172
value: 0x-1374700872
value: 0x-830555768
value: 0x-286253824
ErmaC

Share this post


Link to post
Share on other sites

direct implementation into chameleon

And I always build with make.

Using this inline function

static inline uint64_t getCPUTick(void)
{
    uint32_t lowest;
    uint32_t highest;
    __asm__ volatile ("rdtsc" : "=a" (lowest), "=d" (highest));
    return (uint64_t) highest << 32 | lowest;
}
Later I will do a "battery" test on two different machine

 

EDIT

Test on a i7 920

 

1 Yosemite (i7 920)

value: 2095199764
value: -1651094880
value: -1102424944
value: -559362532
value: -10710116
value: 537801908
value: 1086353572
value: 1635023980
value: -2116924184
value: -1568268356
value: -1019595440
value: -470930884
value: 77735192
value: 620762856
value: 1169414764
value: 1717978568
value: -2028397588
value: -1479723624
value: -936669792
value: -387987268
value: 160707920
value: 709402108
value: 1258049888
value: 1800886892
value: -1945433088
value: -1396757936
value: -848089776
value: -299421888
value: 243634412
value: 792288760
value: 1340968512
value: 1889583764
value: -1856850208
value: -1313944260
value: -765257568
value: -216577364
value: 332079408
value: 880692756
value: 1423521864
value: 1972198292
value: -1774073052
value: -1225381920
value: -676730952
value: -133823380
value: 414825572
value: 963388132
value: 1511989100
value: 2060663536
value: -1691286848
value: -1142627192
value: -593935440
value: -45260392
value: 503398256
value: 1046423544
value: 1595101032
value: 2143765412
value: -1602537528
value: -1053840272
value: -510785500
value: 37749708
value: 586413352
value: 1135091836
value: 1683752264
value: -2068166752
2 Yosemite (i7 920)

value: -1124431036
value: -582142956
value: -39884468
value: 502310872
value: 1038843168
value: 1581112244
value: 2123384832
value: -1629314716
value: -1087083740
value: -550549624
value: -8327536
value: 533934056
value: 1076218084
value: 1618493932
value: -2139914208
value: -1597622832
value: -1055352308
value: -513129028
value: 29041196
value: 565597072
value: 1107856696
value: 1650137508
value: -2102584612
value: -1566083896
value: -1023810616
value: -481609708
value: 60593588
value: 602834496
value: 1139476700
value: 1681657860
value: -2071133752
value: -1528974684
value: -986813804
value: -450165308
value: 92113856
value: 634411564
value: 1176710372
value: 1718993012
value: -2039375456
value: -1497186276
value: -954990568
value: -412760380
value: 129521396
value: 666163644
value: 1208444844
value: 1750710972
value: -2001968536
value: -1465293464
value: -922985780
value: -380726156
value: 161493572
value: 703702200
value: 1240347432
value: 1782588616
value: -1970089452
value: -1427817692
value: -885617000
value: -349079152
value: 193085116
value: 735291936
value: 1277545800
value: 1819854160
value: -1938437336
value: -1396235112

 

Test on a i7 940

1 Yosemite (i7 940)

value: 622136554
value: 1122367582
value: 1629141974
value: 2135876898
value: -1658860070
value: -1152207478
value: -645620118
value: -145385714
value: 361372622
value: 868124366
value: 1368354266
value: 1875060074
value: -1913138046
value: -1412911882
value: -906123458
value: -399415018
value: 100613498
value: 607141574
value: 1113739338
value: 1613965102
value: 2120738346
value: -1667456446
value: -1167228954
value: -660442094
value: -153667450
value: 346560278
value: 853304418
value: 1360067582
value: 1860294570
value: -1928088166
value: -1421489694
value: -921262566
value: -414506498
value: 92290038
value: 592510814
value: 1099102526
value: 1605725850
value: 2105953274
value: -1682286194
value: -1175572530
value: -675544026
value: -168834914
value: 337901450
value: 838123706
value: 1344866734
value: 1851644550
value: -1943096742
value: -1436331022
value: -929554578
value: -429325494
value: 77419130
value: 584197182
value: 1084418222
value: 1591186374
value: 2097884078
value: -1697059722
value: -1190356366
value: -683645678
value: -183621886
value: 323124862
value: 829884322
value: 1330109450
value: 1836836870
value: -1951479050
2 Yosemite (i7 940)

value: 1883145414
value: -1909791522
value: -1401222382
value: -892690630
value: -391297858
value: 116623098
value: 624557586
value: 1125962266
value: 1634233114
value: 2142698806
value: -1650872862
value: -1142922570
value: -634946998
value: -132915762
value: 375683290
value: 884215166
value: 1386240558
value: 1894785518
value: -1891632534
value: -1389609550
value: -881464110
value: -373371454
value: 128648614
value: 637222138
value: 1145633238
value: 1647046578
value: -2140013206
value: -1631885050
value: -1129861482
value: -621749806
value: -113602506
value: 388430126
value: 896457406
value: 1404598898
value: 1906624562
value: -1879817078
value: -1371229062
value: -869196006
value: -360638698
value: 147964158
value: 649977062
value: 1158534862
value: 1667113066
value: -2125814590
value: -1617235046
value: -1108644514
value: -606609110
value: -98074702
value: 410499682
value: 912525514
value: 1421078914
value: 1929658966
value: -1863283830
value: -1354706270
value: -846149654
value: -337612950
value: 164404242
value: 672635686
value: 1180602514
value: 1682630770
value: -2104099478
value: -1596091982
value: -1094060854
value: -585508634

 

ErmaC

Share this post


Link to post
Share on other sites

Can you please use 0x%llx because that will make it easier for me to check.

 

Here we go...

1

 

 

value: 0x786320d4
value: 0x98505e9c
value: 0xb8937de0
value: 0xd8d784f8
value: 0xf93d0370
value: 0x19816c40
value: 0x39707fdc
value: 0x59b58be0
value: 0x79f9c528
value: 0x9a3d0bf4
value: 0xba2ac8dc
value: 0xda6f10ec
value: 0xfab36bf4
value: 0x1af7e0e8
value: 0x3b3c4d50
value: 0x5b2aa57c
value: 0x7b6deff4
value: 0x9bb1dbc8
value: 0xbbf6538c
value: 0xdc3ac954
value: 0xfc295694
value: 0x1c6d36e4
value: 0x3cb14220
value: 0x5cf55b6c
value: 0x7d3896a8
value: 0x9d25bba0
value: 0xbd69b950
value: 0xddae75bc
value: 0xfdf379a8
value: 0x1de1d998
value: 0x3e26173c
value: 0x5e6ae8f4
value: 0x7eafbc60
value: 0x9ef41508
value: 0xbee137e0
value: 0xdf2597fc
value: 0xff6a6504
value: 0x1faf7df8
value: 0x3ff46864
value: 0x5fe199cc
value: 0x8025a92c
value: 0xa06a0e5c
value: 0xc0ae217c
value: 0xe0f155a8
value: 0xe0695c
value: 0x2124c1f4
value: 0x4168dfc0
value: 0x61ac6040
value: 0x81998450
value: 0xa1dc9c04
value: 0xc21fb8bc
value: 0xe2637d24
value: 0x2a80184
value: 0x2296fa38
value: 0x42dbf874
value: 0x63209b78
value: 0x83652afc
value: 0xa3a9b154
value: 0xc39814e8
value: 0xe3dbd324
value: 0x41f364c
value: 0x2462ed58
value: 0x44a818c8
value: 0x649675bc

 

 

2

 

 

value: 0xb0dc47d8
value: 0xd11f7a7c
value: 0xf162edc0
value: 0x1152012c
value: 0x31965d7c
value: 0x51da1450
value: 0x721d46c8
value: 0x926091e8
value: 0xb24fa84c
value: 0xd2949a24
value: 0xf2d96ac8
value: 0x131ddb40
value: 0x336278f4
value: 0x535191c8
value: 0x73962268
value: 0x93daf124
value: 0xb41fe9c0
value: 0xd40e6064
value: 0xf4534780
value: 0x1497f838
value: 0x34dc003c
value: 0x551f498c
value: 0x750db440
value: 0x95516678
value: 0xb595cce8
value: 0xd5dae590
value: 0xf61fe904
value: 0x160d1668
value: 0x3651a510
value: 0x569659a4
value: 0x76dac918
value: 0x971f5874
value: 0xb70d1b58
value: 0xd750423c
value: 0xf79401b8
value: 0x17d89000
value: 0x37c7af08
value: 0x580c0218
value: 0x785071e0
value: 0x98946174
value: 0xb8d7ad58
value: 0xd8c60b94
value: 0xf90933b4
value: 0x194d3164
value: 0x39918ccc
value: 0x59d605a4
value: 0x79c49f44
value: 0x9a08e478
value: 0xba4d9e74
value: 0xda92bca0
value: 0xfad8038c
value: 0x1ac66910
value: 0x3b0ab158
value: 0x5b4efb68
value: 0x7b936dc0
value: 0x9b81ecf8
value: 0xbbc50b74
value: 0xdc09052c
value: 0xfc4db9a4
value: 0x1c92b1e0
value: 0x3c8119c4
value: 0x5cc54f84
value: 0x7d09c280
value: 0x9d4e5144

 

 

ErmaC

Share this post


Link to post
Share on other sites

Ok so there are no 64-bit values. Only 32-bit values so uint32_t is enough.

Yep also work fine with 32 instead of 64 good catch!

 

ErmaC

Share this post


Link to post
Share on other sites
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.

×