View/Open - Oregon State University
Contents
1. In this function we save the instance handle in a global variable and es create and display the main program window BOOL InitInstance HINSTANCE hInstance int nCmdShow HWND hWnd TCHAR szTitle MAX LOADSTRING The title bar text TCHAR szWindowClass MAX LOADSTRING The window class name int result hInst hInstance Store instance handle in our global variable Initialize global strings LoadString hInstance IDC AUDIO szWindowClass MAX LOADSTRING MyRegisterClass hInstance szWindowClass LoadString hInstance IDS APP TITLE szTitle MAX LOADSTRING hWnd CreateWindow szWindowClass szTitle WS VISIBLE CW USEDEFAULT CW USEDEFAULT CW USEDEFAULT CW USEDEFAULT NULL NULL hInstance NULL if hWnd return FALSE ShowWindow hWnd nCmdShow UpdateWindow hWnd if hwndCB CommandBar Show hwndCB TRUE g hWnd hWnd currentBits 8 currentHertz 44100 return TRUE FUNCTION WndProc HWND unsigned WORD LONG 50 PURPOSE Processes messages for the main window WM COMMAND process the application menu WM PAINT Paint the main window WM DESTROY post a quit message and return LRESULT CALLBACK WndProc HWND hWnd UINT message WPARAM wParam LPARAM lParam HDC hdc int wmId wmEvent PAINTSTRUCT ps RECT rt int result GetClientRect g hWnd amp rt switch message case WM COMMAND wmId LOWOR2. format does not compress audio samples however The audio samples held up well to most of the ENT test suite Of all the samples however the deskewed and raw samples seemed to perform the best Of these the 16 bit samples at either 8kHz or 44kHz see Figure 1 Entropy per bit of Audio Samples proved superior The audio samples did not fair as well as the touchscreen in the Monte Carlo estimation of Pi However it appears that the deskewed and fully distilled audio samples performed the best against this test The audio samples produced widely variant results when up against the Serial Correlation Test and very few of them fell in the range given by 7 The only audio samples that satisfied the given acceptable range were 25 e 16 bit 11kHz restaurant e 16 bit 8kHz car e bit llkflz car e 8 bit 22kHz restaurant and e 8 bit 8kHz car A potential reason for this is that large quantities of audio data were collected at once which is not likely to be the preferred implementation for cryptographic purposes It is likely that the data collected from a dynamic pool of audio samples over an extended period of time will produce much better correlation results Such a dynamic pool may be implemented as a stream driver in the Pocket PC operating system which then would not need to be statically or dynamically linked to any particular cryptographic application but available to all 5 2 Analysis of Touchscreen Sampli
3. NULL result 0 return result FUNCTION FileWriterWrite DATE April 2003 PURPOSE Writes a single unisigned integer to the file pointed to by outFile PARAMS data unisgned integer data to be written RETURN a Not initialized O Failure l Success oi 4 int FileWriterWrite char data int result 1 if outFile NULL if fprintf outFile c data sizeof data result 0 else 45 result 1 J return result int FileWriterNewline void int result 1 if outFile NULL fprintf outFile n else result 0 return result J int FileWriterComma void int result 1 if outFile NULL forantf out le TT else result 0 return result FUNCTION FileWriterClose DATE April 2003 PURPOSE Closes the file pointer and frees any used memory that may have been allocated PARAMS NONE RETURN l Not initialized X O Failure 1 Success N int FileWriterClose void int result 1 if outFile NULL if fclose outFile 0 result 0 else result 1 return result 46 audio h if defined AFX AUDIO H_68F81C24 E17E 412B 99F8 7BCF206FE788 IN CLUDED define AFX AUDIO H 68F81C24 E17E 412B 99F8 7BCF206FE788 INCLUDED if MSC VER gt 1000 pragma once endif MSC VER gt 1000 include resource
4. include lt sys stat h gt include lt sys types h gt include lt unistd h gt define MAX DESKEW BUFFER SIZE 1048576 L4 Meg void DeskewUsage void int main int argc char argv char inFilePath argv 1 char outFilePath argv 2 unsigned char readBuffer MAX DESKEW BUFFER SIZE unsigned char writeBuffer MAX DESKEW BUFFER SIZE int eofFlag 0 unsigned char temp 1 unsigned char a unsigned char b mode t mode int inFile handle to input file int outFile handle to output file int count counts bytes read from input file int packCount tracks bits that have been packed int idx index for output buffer 61 int g byte loop index int Jes 74 bit loop index unsigned char maskArray 8 0x01 0000 0001 0 0x02 0000 0010 1 0x04 0000 0100 2 0x08 0000 1000 3 0x10 0001 0000 4 0x20 0010 0000 5 0x40 0100 0000 6 0x80 1000 0000 7 ys Check that enough arguments were supplied otherwise print usage if argc gt 3 mode S IRUSR S IWUSR S IRGRP S IWGRP S IROTH inFile open inFilePath O RDONLY mode outFile open outFilePath O WRONLY O EXCL O CREAT mode Detect error opening input file if inFile 1 perror inFile return 1 Detect error opening output file if outFile 1 perror outFile return 1 packCount 0 62 ifdef DEBUG pr
5. 3 Open file handles mode S IRUSR S IWUSR S IRGRP VN S IWGRP S IROTH inFile open inFilePath O RDONLY mode outFile open outFilePath O WRONLY O CREAT mode check inFile if inFile 1 perror inFile return 1 check outFile if outFile 1 perror outFile return 1 Read the entire file into buffer while amtRead read inFile temp 1 gt 0 buffer i temp 0 count amtRead ltt Return an error if the input file contains fewer bytes than the truncation amount if count lt truncAmt perror inFile too small return 1 68 Write truncated amount to outFile write outFile buffer truncAmt Close file streams close inFile close outFile else Display proper usage TruncFileUsage return 0 void TruncFileUsage printf nn printf USAGE n printr printf printf truncfile lt infile gt lt outfile prefix gt lt truncation amount in bytes gt n NOTE The last argument to truncfile cannot be checked for errors n therefore the output file size must be checked prior to use n printf n n
6. Entropy per bit of Audio Samples 2 eere eee 17 2 Entropy per bit of Touchscreen Samples ees 18 3 Average Entropy per bit of Audio Samples eese 19 4 Arithmetic Mean of Audio Samples eese 20 5 Arithmetic Mean of Touchscreen Samples esses 20 6 Monte Carlo Estimation of Pi for Audio Samples mueve 21 7 Monte Carlo Estimation of Pi for Touchscreen Samples 21 8 Serial Correlation of Audio Samples eere 22 9 Serial Correlation of Touchscreen Samples s eeesuuss 23 10 Average Serial Correlation of Audio Samples 23 11 Chi Square Test Results for 16 Bit Audio Samples RAW 28 12 Chi Square Test Results for 16 Bit Audio Samples DESKEWED 29 Random Number Generation on Handheld Devices for Cryptographic Applications 1 Introduction Today s cryptographic applications securing some of our most critical infrastructures and communications rely heavily upon random data In most cases they rely upon pseudo random data Generation of random data can occur in one of two ways naturally or deterministically The latter is the most common because most cryptosystems are employed on digital machines i e computers Determinis
7. Manual October 2001 7 D E Knuth The Art of Computer Programming Volume 2 Addison Wesley Third Edition 1998 8 A Menezes Handbook of Applied Cryptography CRC Press 1996 9 Motorola Inc MC68328 DragonBall Integrated Processor User s Manual 1995 10 National Institute of Standards and Technology Specifications for the Data Encryption Standard DES October 1999 11 National Institute of Standards and Technology Specification for the Advanced Encryption Standard AES November 2001 12 Andrew Rukhin Juan Soto James Nechvatal Miles Smid Elain Barker Stefan Leigh Mark Levenson Mark Vangel David Banks Alan Heckert James Dray San Vo A statistical test suite for random and pseudorandom number generators for cryptographic applications Technical report National Institute of Standards and Technology May 2001 13 Bruce Schneier Applied Cryptography John Wiley and Sons Inc Second Edition 1996 33 14 William Stallings Cryptography and Network Security Principles and Practice Prentice Hall Inc Second Edition 1999 15 Douglas R Stinson Cryptography Theory and Practice Chapman and Hall Second Edition 2002 16 Stephen Thomas SSL and TLS Essentials John Wiley and Sons Inc 2000 17 U S Department of Commerce National Institute of Standards and Technology Digital Signature Standard DSS January 2000 APPENDICES 34 35 This section contains the sourc
8. Next default values for new objects ifdef APSTUDIO INVOKED ifndef APSTUDIO READONLY SYMBOLS define APS NEXT RESOURCE VALUE 104 define _APS NEXT COMMAND VALUE 40042 define APS NEXT CONTROL VALUE 1001 define _APS NEXT SYMED VALUE 101 tendif tendif StdAfx h stdafx h include file for standard system include files Or project specific include files that are used frequently but are changed infrequently if defined AFX STDAFX H A9DB83DB A9FD 11D0 BFD1 444553540000 I NCLUDED i o define AFX STDAFX H A9DB83DB A9FD 11D0 BFD1 444553540000 INCLUDED _ if MSC VER gt 1000 pragma once Kendif MSC VER gt 1000 define WIN32 LEAN AND MEAN Exclude rarely used stuff from Windows headers Windows Header Files include lt windows h gt include commctrl h include lt stdio h gt Local Header Files include audio h include sound recorder h include file writer h include os rand h tinclude ir rand h include prng ppc sha h TODO reference additional headers your program requires here 37 AFX_INSERT LOCATION Microsoft eMbedded Visual C will insert additional declarations immediately before the previous line endif defined AFX STDAFX H A9DB83DB_A9FD_11D0 BFD1 444553540000 I NCLUDED StdAfx cpp stdafx cpp source file that includes just the standard includes T audio pch will be the pre compiled header stdafx obj will
9. Presented May 21 2003 Commencement June 2004 Master of Science thesis of Adam W Montville presented on May 21 2003 APPROVED Redacted for Privacy Major Professor representing Electri Computer Engineering Redacted for Privacy Director of School of Electrical Enginesfing and Computer Science Redacted for Privacy Dean of Graduate School T I understand that my thesis will become part of the permanent collection of Oregon State University libraries My signature below authorizes release of my thesis to any reader upon request Redacted for Privacy J Adam W Montville Author ACKNOWLEDGEMENTS First I thank God for providing me with the determination perseverence and will to complete this thesis I also thank my Major Professor Dr Cetin K Koc for his guidance and helpful criticism throughout the research of this topic In addition this work could not have been completed if it were not for my future wife Virginia Without her none of this would have been possible My gratitude is not complete without thanking my father who always offered his assistance in proofing and mastering the English language Finally I thank Daniel Montville for loaning me hardware test equipment it may have been old but it worked To those who should have been named but weren t please forgive my forgetfulness and know that I appreciate a those who lent a helping hand to my research whether directly or indirectly
10. SETTING AMT 100K MENUITEM 250 KB IDM SETTING AMT 250K MENUITEM 512 KB IDM SETTING AMT 512K MENUITEM 1 MB IDM SETTING AMT 1M END END END MEM MMMMMIMMMMMMMMMIMMIMMEMIMMMMMMMIMIMIMMMMMMMMIMMIMMMMIMMEMMI M MIMMMIMMMMMMMIME Dialog IDD ABOUTBOX DIALOG DISCARDABLE 0 0 125 55 STYLE DS MODALFRAME WS POPUP WS CAPTION WS SYSMENU EXSTYLE 0x80000000L CAPTION About audio FONT 8 System BEGIN ICON IDI AUDIO IDC STATIC 11 17 20 20 LTEXT audio Version 1 0 IDC STATIC 38 10 70 8 538 NOPREFIX LTEXT Copyright C 2003 IDC STATIC 38 25 70 8 END MIEMP Pg MMEMMMMMMMIMMMMMMMP PMMIMIMMMMMMMMIIMMMMMIMIMIMMMMMMMMMM 1 1 11 111 DESIGNINFO ifdef APSTUDIO INVOKED GUIDELINES DESIGNINFO DISCARDABLE BEGIN IDD ABOUTBOX DIALOG BEGIN 41 LEFTMARGIN 7 RIGHTMARGIN 118 TOPMARGIN 7 BOTTOMMARGIN 48 END END tendif APSTUDIO INVOKED 114111411114119J91111 F117 IASI AIA LAT TIA IA II TI 149 VAI III TAIT TIS TT 11414137174 14114 Accelerator IDC AUDIO ACCELERATORS DISCARDABLE BEGIN go aor IDM HELP ABOUT ASCII ALT NOINVERT VK F4 IDM FILE EXIT VIRTKEY AIT NOINVERT END FIDTSIITT ESATA II ASATAIS IIIA TIT LIASAL TAT IA TIT AI ITAA III IIIS TITS TT FILATELIA 14 1 String Table STRINGTABLE DISCARDABLE BEGIN IDS APP TITLE audio IDS HELLO Hello World IDC AUDIO AUDIO END endif English U S resources LITTI
11. h endif defined AFX AUDIO H 68F81C24 E17E 412B 99F8 7BCF206FE788 IN CLUDED audio cpp audio cpp Defines the entry point for the application Pi tinclude stdafx h define MAX LOADSTRING 100 Global Variables HINSTANCE hInst The current instance HWND hwndCB The command bar handle HWND g_hWnd TCHAR szOut MAX LOADSTRING String to be output B BOOL dataCollected FALSE indicates whether data has been collected BOOL first TRUE Ti Indicates first run BOOL working FALSE BOOL audioDataCollected BOOL trackEnabled FALSE BOOL audioEnabled FALSE BOOL irEnabled FALSE BOOL osEnabled FALSE enum TASKS NONE AUDIO IR OS TRACK CHAR seedBuffer TASKS running NONE 47 UINT dataCount int currentBits int currentHertz char outFileName rand txt TCHAR errorMessage MAX LOADSTRING BOOL errorPresent FALSE UINT myError SEED DATA prngData UINT tsDelay 25 default UINT dataCollectionAmount 1024 default DWORD threadId DWORD threadExitCode Forward declarations of functions included in this code module ATOM MyRegisterClass HINSTANCE LPTSTR BOOL InitInstance HINSTANCE int LRESULT CALLBACK WndProc HWND UINT WPARAM LPARAM LRESULT CALLBACK About HWND UINT WPARAM LPARAM void AudioCallback void LRESULT DoMouseMain HWND hWnd UINT wMsg WPARAM wParam LPARAM lParam void LoggerFunctio
12. including you TABLE OF CONTENTS INIBODUCLIION Gc uses chai evens cha sue eens 1 2 Background DS Gel 4 2 1 Sources of Randomness eiecti eer dd ic oee eara EEEE ESE 4 2 2 MMandheld DeVieesa cse o RE stie s 6 3 Materials and Methods nci EL HERE reete td ee as 7 3 1 The Seed Goal 7 32 Random Bit Collection Source eese eene ene 7 3 3 Handheld Implementation Platform 8 3 4 Audio Data Collection eere eee e eese eerte nennt etos 10 dd Test Method uu iier eh aetate terit ds 12 3 6 Quantity of Collected Data esee 16 T RESUMS css las s sii E ELI EA Ss D 17 Als BNWOPV SUMAUOD ene etii eise tet EE eo ve teeth aaa Eie 17 42 Arithmetic Mean trio e ies 19 4 3 Monte Carlo Estimation of Pi eene 20 44 Soral COrfel li0fhv sadd esam aede gs osis 22 Di DISCUSSION sads and tee een Que 24 5 l Analysis of Audio Sampling esee 24 5 2 Analysis of Touchscreen Sampling esses 25 5 3 Chi Sguare Distribution Analysis cese 27 0 UII PNE UN E 29 61 General CONCIUSIONS oet Go epi oii ISOLE ai 30 6 2 Recommendations for Future Work eese 31 RETE NOES ioris emo ss 32 LIST OF FIGURES FIGURE PAGE 1
13. it would be advantageous for any practical implementation to avoid if possible 17 distillation measures for the sake of processing time reduction and there for a reduction in power consumption 4 Results 4 1 Entropy Estimation The entropy per bit range of the results extend from approximately 0 78 to 1 0 which yields approximately 6 24 to 8 bits of entropy randomness per byte Figure 1 Entropy per bit of Audio Samples shows the entropy per bit of the audio samples at all levels of distillation and Figure 2 Entropy per bit of Touchscreen Samples shows the entropy per bit of the touchscreen samples at all levels of distillation Audio Samples 1 002000 qu 1 000000 IS Car Classroom OOffice KJRestaurant Entropy per Bit o o S 18 bit 11kHz 16 bit 22kHz 16 bit 44kHz 16 bit 8kHz 8 hit ilkHiz B bit22kHz 8 bit 44kHz B bit 8kHz Source and Distillation Figure 1 Entropy per bit of Audio Samples 18 Touchscreen 1 002000 1 000000 0 998000 EE 0 996000 SS Sms g Oms J ms scs E Es E E nl E Ertimate d Entrupy por Bit Deskewed Entropy Deskewed Entropy Raw Distillation Figure 2 Entropy per bit of Touchscreen Samples Figure 1 Entropy per bit of Audio Samples is somewhat difficult to interpret so Figure 3 Average Entropy per bit of Audio Samples shows the average estimated entropy per bit of all audio sample configurations i e sample size
14. next pair otherwise store as an output of the generator and discard f before iterating This method of deskewing produces unbiased output from any generator 8 14 3 5 2 Selected Suite The test suite chosen for this study is the ENT Test Suite The ENT Test Suite is comprised of the Chi Square Distribution Test Arithmetic Mean Test Monte Carlo Estimation of Pi and the Serial Correlation Test In addition to these specific tests the estimated entropy per bit is also given by the selected test suite The test suite was chosen because it is suitable for testing random seed data 3 5 2 1 Chi Square Distribution Test The Chi Square Distribution Test is perhaps the most common test of randomness available It is also used as a foundation for other randomness tests 12 The distribution is calculated for the input stream and represented as an absolute value and a percentage where the percentage indicates the frequency at which a truly random sequence uniformly distributed would exceed the absolute value 7 The interpretation of such results lies in the interpretation of the given percentage the percentage is taken to be the degree to which the sequence is suspected of being non random 7 A sequence is judged to be non random if the given percentage is greater than 99 or less than 1 A sequence is suspected of being non Much of the information contained in this section is not intended to describe the te
15. temp ptM x LOWORD lParam ptM y HIWORD 1Param if dataCount dataCollectionAmount temp ptM x amp OxOOFF ptM y amp OxOOFF collect the xor of low bytes FileWriterWrite temp dataCount else dataCollected TRUE dataCount 0 RECT rt GetClientRect g hWnd amp rt InvalidateRect g hWnd amp rt TRUE hdc GetDC hWnd SetPixel hdc ptM x ptM y RGB 0 0 0 SetPixel hdc ptM x 1 ptM y RGB 0 0 0 SetPixel hdc ptM x ptM y 1 RGB 0 0 0 SetPixel hdc ptM x 1 ptM y 1 RGB 0 0 0 ReleaseDC hWnd hdc Sleep tsDelay return O0 58 j FUNCTION PackSeedData DATE April 2003 PURPOSE Take one bit of entropy collected and pack these bits into words for use in PRNG PARAMS NONE RETURN NONE NOTE Assumes that the raw seed data has already been collected Tus void PackSeedData int i j k temp int mask 0x00000001 prngData c len 60 prngData t len 20 for i 0 i lt 60 i for j 1 B J lt itij 0 JF d temp seedBuffer j amp mask prngData c i prngData c i temp prngData c i lt lt 1 i now equals 60 for i i lt 80 i forik D J i87 j lt 141 8 JT kf 4 temp seedBuffer j amp mask prngData t k prngData t k temp prngData t k lt lt 1 FUNCTION LoggerFunction DATE April 2003 59 PURPOSE Allows other components to wri
16. AN ABSTRACT OF THE THESIS OF Adam W Montville for the degree of Master of Science in Electrical and Computer Engineering presented on May 21 2003 Title Random Number Generation on Handheld Devices for Cryptographic Applications Abstract Approved Redacted for Privacy Cetin K Koc Random number generation is important in many fields today It is particularly important in the field of cryptography when generating nonce values cryptographic keys and other data required in many cryptographic applications The proliferation of small handheld devices that are typically connected to large networks via a wireless connection requires stringent security Because it may be easier to attack a pseudorandom number generator than to attack a particular cryptosystem it is important that the generation of random numbers on handheld devices be as secure as possible In order for the random number generator to provide good secure random data it must first be seeded by a value that itself possesses the qualities of a good random sequence This paper explores several potential seed sources that are available on many current handheld devices Copyright by Adam W Montville May 21 2003 All Rights Reserved Random Number Generation on Handheld Devices for Cryptographic Applications by Adam W Montville A THESIS submitted to Oregon State University in partial fulfillment of the requirements for the degree of Master of Science
17. D wParam wmEvent HIWORD wParam Parse the menu selections Switch wmId case IDM HELP ABOUT DialogBox hInst LPCTSTR IDD ABOUTBOX hWnd DLGPROC About break case IDM FILE EXIT DestroyWindow hWnd break case IDM SETTING TS 10 tsDelay 10 break case IDM SETTING TS 15 tsDelay 15 break case IDM SETTING TS 5 tsDelay 5 break case IDM SETTING AMT 1K dataCollectionAmount break case IDM SETTING AMT 5K dataCollectionAmount break case IDM SETTING AMT 10K dataCollectionAmount 10240 break li 1024 li 5120 case case case case Case Case amp AudioPowerManageSubversion TRUE SoundRecorderInitialize outFileName DWORD AudioCallback amp rt TRUE case TRUE case TRUE case IDM SETTING AMT 50K dataCollectionAmount break IDM SETTING AMT 100K dataCollectionAmount break IDM SETTING AMT 250K dataCollectionAmount break IDM SETTING AMT 512K dataCollectionAmount break IDM SETTING AMT 1M dataCollectionAmount break IDM RUN_1MB dataCollected running AUDIO iu It FALSE 51 51200 102400 256000 5120005 1048576 CreateThread NULL NULL NULL 0 amp threadId InvalidateRect g hWnd result if result 1 rt dataCollectionAmount SoundRecorderStart working TRUE else running NONE InvalidateRect g hWnd break IDM RUN TOUCH if dataCollecte
18. ITITTITALI IAA TAI TS SSS SSS S TATA STS ATT IAAT TA AIA ST SDS AIST ATI AAT ASAT VI ifndef APSTUDIO INVOKED TIF TID dd dd IIIS ATA FI TAIT IT ISI LI AIT dk AA STAT AA IA AA TA SI ATI M L MMIMIMMMMMPM Generated from the TEXTINCLUDE 3 resource IT 42 VISIT PITATTTA TIAA AT EPAPTA TALS AA LALA TAS IAT I AI IATA USS S TILT TT ILLIA ILALL ITAA endif not APSTUDIO INVOKED newres h ifndef _NEWRES_H define NEWRES H _ if defined UNDER _CE define UNDER CE _WIN32 _WCE tendif if defined WIN32 WCE tif defined WCEOLE ENABLE DIALOGEX define DIALOGEX DIALOG DISCARDABLE endif tinclude commctrl h tdefine SHMENUBAR RCDATA tif defined WIN32 PLATFORM PSPC amp amp WIN32 WCE gt 300 include lt aygshell h gt else define I IMAGENONE 2 tdefine NOMENU OxFFFF define IDS SHNEW 1 define IDM SHAREDNEW 10 tdefine IDM SHAREDNEWDEFAULT 11 tendif Kendif WIN32 WCE ifdef RC INVOKED ifndef INC WINDOWS define _INC_WINDOWS include winuser h extract from windows header endif tendif ifdef IDC STATIC undef IDC STATIC tendif tdefine IDC STATIC 1 endif NEWRES H _ 43 file_writer h f Ck e che ke e e ehe ee he ehe e e ke he ke ke he ke ehe ke ke ke he khe e ehe e ehe ehe ee e ee e e e ke ee ke ke ee e kKkekkkkkkkkek FILE file writer h PURPOSE Header information for file writer c DATE April 2003 AUTHOR Adam W Montville Information
19. O INVOKED M IM M M MMMMIMMMMMMMMMMMMMMMMMMMMMMMIMMMIMIMMIMMEMMMMUMIMMMM f M l MI M PMMMIMEIMM Menubar IDM MENU MENU DISCARDABLE BEGIN POPUP amp File BEGIN MENUITEM E amp xit IDM FILE EXIT END 39 POPUP amp Help BEGIN MENUITEM amp About IDM HELP ABOUT MENUITEM Instructions IDM INSTRUCTION END POPUP Run BEGIN MENUITEM Collect raw Audio IDM RUN_1MB MENUITEM Collect raw Touchscreen IDM RUN TOUCH MENUITEM Collect PRNG from OS IDM RUN OS RAND MENUITEM Collect raw IR IDM RUN IR MENUITEM SEPARATOR MENUITEM Get PRN from Audio IDM RUN RAND AUD MENUITEM Get PRN from Touchscreen IDM RUN RAND TS MENUITEM Get PRN from OS IDM RUN RAND OS MENUITEM Get PRN from IR IDM RUN RAND IR END POPUP Settings BEGIN POPUP AUDIO BEGIN MENUITEM 16 Bit Samples IDM SETTING 16 BIT MENUITEM 8 Bit Samples IDM SETTING 8 BIT MENUITEM 8 kHz IDM SETTING 8 KHZ MENUITEM 11 kHz IDM SETTING 11 KHZ MENUITEM 22 kHz IDM SETTING 22 KHZ MENUITEM 44 kHz IDM SETTING 44 KHZ END POPUP Touchscreen BEGIN MENUITEM 15 ms delay IDM SETTING TS 15 MENUITEM 10 ms delay IDM SETTING TS 10 MENUITEM 5 ms delay IDM SETTING TS 5 END POPUP Data Collection Amount BEGIN 40 MENUITEM 1 KB IDM SETTING AMT 1K MENUITEM 5 KB IDM SETTING AMT 5K MENUITEM 10 KB IDM SETTING AMT 10K MENUITEM 50 KB IDM SETTING AMT 50K MENUITEM 100 KB IDM
20. Security Laboratory Oregon State University montviad ece orst edu KK KKK KKK IKK KKK KKK KKAKKAKKK KKK KK Kh KK kt KK Kh kkk kkk kkk kkk kkk kk kkk kv kx Sk ko kk kkkkkkkkkk ifndef FILE WRITER define FILE WRITER include stdafx h FUNCTION DECLARATIONS See Implementation for descriptions int FileWriterInitialize char int FileWriterWrite char int FileWriterClose void int FileWriterNewline void int FileWriterComma void endif FILE WRITER file_writer cpp f ke he e e ee hee e dee k k e ee k k he ee ee de e e e e e hee he k k he k k e ee e ee e k k ee e e k e e e k e k kKakkkkkk dd FILE file writer c PURPOSE Interface for writing files when collecting PRNG seed data This interface uses the standard C style file functions DATE April 2003 AUTHOR Adam W Montville Information Security Laboratory Oregon State University montviad ece orst edu Ke KH HK HK HK HK KKK KK KKK kd HK KK KKK kt dk kt KKH KIKI KKK dk kk kk ke ko ko ko kt ki kkkkkkkkkk include lt stdio h gt include file writer h FILE outFile File pointer FUNCTION FileWriterInitialize DATE April 2003 PURPOSE Initialize the file writing component for Operation PARAMS filePath character pointer to file RETURN 0 Failure l Success 4 int FileWriterInitialize char filePath int result 1 outFile fopen filePath w open for writing if outFile
21. an adversary and the employed PRNG generates acceptable sequences then the adversary is not likely to predict the output of the PRNG Therefore the layer below for a given PRNG is the seeding of that PRNG If the seed is somehow known then the PRNG is predictable Predictability occurs when an adversary can determine the generated numbers before they are generated If the PRNG is predictable then the key may be predictable If the key is predictable then the cryptographic application is insecure Ultimately the seed must be just as unpredictable as the output of the PRNG 12 In order to get a seed that is unpredictable without requiring another seed it is necessary to find some naturally occurring source of random information 2 Background 2 1 Sources of Randomness Randomness can come from many places A person sitting on a park bench flipping a quarter can provide a source of randomness though that may be arguably too slow for any cryptographic application requiring a random bit sequence A very well known source of randomness comes from the rate of radioactive decay A computer system running an operating system and having some form of a user interface may provide several sources of randomness 8 e Hardware based external generators o Audio video input o Disk drives o Thermal noise or other hardware noise e Software based internal generators o Keyboard mouse movements o VO buffer content o Operating system s
22. and rate at all levels of distillation 19 Audio Samples Burrage Eoliastiod Evl opat sl Sampie Configuration Figure 3 Average Entropy per bit of Audio Samples 4 2 Arithmetic Mean These are the results of the ENT Arithmetic Mean Test Recall that a value close to 0 5 is desired for a random sequence Figure 4 Arithmetic Mean of Audio Samples shows the arithmetic mean of the audio samples at all levels of distillation and Figure 5 Arithmetic Mean of Touchscreen Samples shows the arithmetic mean of the touchscreen samples at all levels of distillation 20 Audio Samples RT amp Sai sed d C sy tt 3 T i H 1 D ED E R D ED E R p Eo E R b Ep e R en E D 16 hit fikHz 16 hit 22kHz 16 bit 4dkHz 16 bit 8kHz Bbt llkHz Bit kHz amp Lit 44kHz B bt 8kHz Conf igur aiton and Distillation Figure 4 Arithmetic Mean of Audio Samples 0 580000 perme 0 560000 JS 0 540000 IS 0 520000 Arithmetic Mean 0 480000 SS 0 460000 EE Figure 5 Arithmetic Mean of Touchscreen Samples 4 3 Monte Carlo Estimation of Pi These are the results of the Monte Carlo Estimation of Pi The closer the estimation comes to Pi the more random the sequence is assumed to be Figure 6 Monte Carlo Estimation of Pi for Audio Samples shows the 2l estimation of the audio samples at all levels of distillation and Figure 7 Monte Carlo Estimation of Pi for Touchscreen Sa
23. ataCount Q myError FileWriterInitialize outFileName if myError swprintf szOut TEXT COULD NOT INIT OUTFILE else swprintf szOut TEXT Scribble as randomly as possible DrawText hdc szOut _tcslen szOut amp rt DT LEFT DT WORDBREAK else FileWriterClose swprintf szOut TEXT Touchscreen data collected DrawText hdc szOut _tcslen szOut amp rt DT LEFT DT WORDBREAK AUDIO COLLECTION IS RUNNING else if running AUDIO if dataCollected swprintf szOut TEXT Collecting audio data DrawText hdc szOut _tcslen szOut amp rt DT LEFT DT WORDBREAK else GetExitCodeThread amp threadId amp threadExitCode ExitThread threadExitCode 55 swprintf szOut TEXT Data has been collected DrawText hdc szOut _tcslen szOut amp rt DT LEFT DT WORDBREAK EndPaint hWnd amp ps break case WM LBUTTONDOWN case WM MOUSEMOVE if running TRACK if dataCollected DoMouseMain hWnd message wParam lParam break case WM DESTROY CommandBar Destroy hwndCB PostQuitMessage 0 break default return DefWindowProc hWnd message wParam lParam return 0 Mesage handler for the About box LRESULT CALLBACK About HWND hDlg UINT message WPARAM wParam LPARAM lParam RECT rt rtl int DlgWidth DlgHeight dialog width and height in pixel units int NewPosX NewPosY Switch
24. contain the pre compiled type information include stdafx h TODO reference any additional headers you need in STDAFX H and not in this file audio rc Microsoft Developer Studio generated resource script hf include resource h define APSTUDIO READONLY SYMBOLS VATISTA ISI T ITIL ATI TAIL TS PIII A TI SATII III TTI aT IT TTU 1 1 111 11 1 Generated from the TEXTINCLUDE 2 resource include newres h PIPTATLATLATT ITA T AL TT AT LATIF EPEAT ASAT TAS TAS TATA TAS TITAS T I DE LTK undef APSTUDIO READONLY SYMBOLS PITIPISIITIT IIS LIILIA ILILILILIL tddlttid 1414 kd English U S resources Rif defined AFX RESOURCE DLL defined AFX TARG ENU ifdef WIN32 LANGUAGE LANG ENGLISH SUBLANG ENGLISH US pragma code page 1252 endif WIN32 38 M M M M MM MM M M M M M MM MMgMMMMM MM M MH MH M MH M M M M M M M M M M M M M M M M MTM MT M M M MMMMGA OAHMMMH f M l MIMIMMM EMMM Icon Icon with lowest ID value placed first to ensure application icon remains consistent on all systems IDI AUDIO ICON DISCARDABLE audio ICO ifdef APSTUDIO INVOKED MEM MM M MMMMMMMMMgMMMMMMMMPMMMMMMMMIMMEMIIEMMMMMMIAMMMMMMIM 1 1 f 1 TEXTINCLUDE 4 1 TEXTINCLUDE DISCARDABLE BEGIN resource h 0 END 2 TEXTINCLUDE DISCARDABLE BEGIN include newres h r n V 6 a END 3 TEXTINCLUDE DISCARDABLE BEGIN ArAn nO END endif APSTUDI
25. ctionality Of particular importance is the fact that every Pocket PC device is required to have a source of audio input and a touchscreen as part of the user interface The particular Pocket PC device used in this study was a Dell Axim X5 with an Intel XScale microprocessor 32MB of internal RAM 32MB of Intel StrataFlash non volatile memory and running Pocket PC 2002 3 3 1 Software Implementation Several software components were required to complete this study These components fall into two primary categories Pocket PC Software and Test and Evaluation Software The Pocket PC Software was originally implemented for the sole purpose of data collection and has now been slightly rewritten to form a cohesive Application Programming Interface that can be included in derivative works see the Appendix for source listings 3 3 1 1 Pocket PC Software 3 3 1 1 1 Touchscreen Data Collection The touchscreen on a Pocket PC is intended to be the primary user interface on the device The screen resolution of all Pocket PC devices is specified by Microsoft to be 240 x 320 pixels Touchscreen data can be collected as entropy by looking at the varying coordinates of the stylus upon the touchscreen as time passes The implementation used for this study requires the user to scribble on the screen as randomly as they can and then collects the points of the stylus on the touchscreen at various sample rates wherein the software collects poi
26. d dataCount 0 w A dataCollected running TRACK InvalidateRect g hWnd FALSE break IDM RUN OS RAND dataCollected running OS InvalidateRect g hWnd FALSE break IDM RUN IR dataCollected FALSE TRUE amp rt amp rt 52 running IR InvalidateRect g hWnd amp rt TRUE break case IDM SETTING 8 BIT SoundRecorderSet Format 8 currentHertz break case IDM SETTING 16 BIT SoundRecorderSetFormat 16 currentHertz break case IDM SETTING 8 KHZ SoundRecorderSetFormat currentBits 8000 break case IDM SETTING 11 KHZ SoundRecorderSetFormat currentBits 11025 break case IDM SETTING 22 KHZ SoundRecorderSetFormat currentBits 22050 break case IDM SETTING 44 KHZ SoundRecorderSetFormat currentBits 44100 break default return DefWindowProc hWnd message wParam lParam break case WM CREATE hwndCB CommandBar Create hInst hWnd 1 CommandBar InsertMenubar hwndCB hInst IDM MENU 0 CommandBar AddAdornments hwndCB 0 0 break case WM PAINT RECT rt hdc BeginPaint hWnd amp ps GetClientRect hWnd amp rt rt top rt top 30 make room for command bar if errorPresent 53 DrawText hdc errorMessage tcslen errorMessage amp rt DT LEFT DT WORDBREAK errorPresent FALSE else NOTHING IS YET RUNNING if running NONE Swprintf szOut TEXT Select the desired
27. dio Samples Average Serial Correlation E ti Am 7 ex s M MES 4 D A Eo d i 1 gt ii z DEA 2 or Aen ea a E 4 i r p e x 4 5 ey i i 7 f R 5 1 x zc r we LEN g x E Ad E 1 E k t 2 PA e f lt 1 a F ENS 2 m a t E 3 k a m i d 1 7 1 M 5 A J x 4 4 Ed 4 2 x e f i 21 E a Ti zi rl gt i vt m 7 Um x 3 S i TA A A J gt kr 4 v Rat 1 A L 4 4 oh Poe q Tx 5 d aie ea va R a Ju cM ed 18 bit 11 kHz 16 bit Z2kHz 16 bit 44kHz 16 bit BkHz 8 bit11kHz 8 hit 27kHz Sbit 44XHz 8 bit 8kHz Source Configuration Figure 10 Average Serial Correlation of Audio Samples sample size M Deskewed lEnvDeskewed D Entropy DRaw 24 5 Discussion 5 1 Analysis of Audio Sampling Prior to testing it was thought that the audio e would reguire extensive distillation in order to achieve randomness One reason for this prejudice stems from the thought that the audio input hardware on the handheld device was likely to have some filtering to reduce noise Another reason is that the audio hardware is not directly accessible Rather the operating system had to be used as the interface to the audio hardware and it was thought that the operating system might further filter the sample input or otherwise alter the data prior to testing As mentioned in 1 the WAV file
28. e return 1 J if outFile 1 perror outFile return 1 count while read inFile temp 1 gt 0 toWrite 0 towrite 0 temp 0 amp mask if count 8 toWrite 0 toWrite 0 lt lt 1 counttt else count 1 write outFile toWrite 1 close inFile 66 close outFile else CollectEntropyUsage return O0 void CollectEntropyUsage printf WMnMn printf USAGE n printf colent infile lt outfile gt n printf An Mn trunc files c TRUNC FILES C AUTHOR A W Montville VERSION 1 0 Given an input file this will truncate the file to a T7 user defined byte length Copyright c 2003 A W Montville F include lt fcntl h gt include lt stdio h gt include lt stdlib h gt include sys stat h include lt sys types h gt include lt unistd h gt ifndef TRUNC FILE MAX BUFFER SIZE define TRUNC FILE MAX BUFFER SIZE 2097152 2 MB buffer tendif Function Prototypes void TruncFileUsage void Main program entry int main int argc char argv 67 char inFilePath argv 1 char outFilePath argv 2 char temp 1 char buffer TRUNC FILE MAX BUFFER SIZE int inFile outFile int i 0 int count 0 int amtRead 0 int truncAmt 0 mode t mode Check that enough arguments were supplied otherwise print usage if argc gt 4 truncAmt atoi argv
29. e an automobile of some kind on a day to day basis Dining in a restaurant is thought to have been a good simulation of any busy location such as an airport terminal Lecture attendance is not unlike attending a presentation or group meeting where roughly one person speaks at a time Finally the quiet office is the environment in which only typing printing body movements and background noise are picked up by the audio recording device These locations are referred to as location sources or SOurces 12 For each of the collection locations eight different samples were taken The Wave API provides for two sample sizes 8 bit and 16 bit For each sample size there are four sample rates available 8kHz 11kHz 22kHz and 44kHz This yields a total of eight sample configurations for each of the location sources 3 4 1 1 Test and Evaluation Software Several small software components were implemented to assist in organizing the collected data for testing Without going into too much detail three tools were implemented for the Linux operating system deskew colent and truncfile Each of these tools take a user supplied data file manipulate the data contained in the file then write the final result to a new user specified file The deskew command is used for removing bias from collected data colent is used to collect one bit of entropy for every byte in the collected data file and truncfile is used to trim a given data file to a
30. e listings for all code developed for this research The code 1s divided into two sections Pocket PC and Linux Pocket PC Source Listings Resource h define IDS_APP_TITLE 1 define IDS HELLO 2 define IDC AUDIO 3 define IDI AUDIO 101 define IDM MENU 102 define IDD ABOUTBOX 103 define IDM FILE EXIT 40002 define IDM_ HELP _ABOUT 40003 define IDM _RUN_1MB 40004 define IDM RUN 2MB 40005 define IDM RUN_ 4MB 40006 define IDM RUN 8MB 40007 define IDM_ RUN 16MB 40008 define IDM RUN 32MB 40009 define IDM SETTING 16 BIT 40010 define IDM SETTING 8 BIT 40011 define IDM SETTING _ 8 _ KHZ 40012 define IDM SETTING _ 11 _ KHZ 40013 define IDM SETTING _ 22 _ KHZ 40014 define IDM SETTING 44 _ KHZ 40015 define IDM RUN _ TOUCH 40016 define IDM RUN OS RAND 40017 define IDM RUN IR 40018 define IDM SETTING GEN DATA 40021 define IDM RUN RAND AUD 40022 define IDM RUN RAND TS 40023 define IDM RUN RAND OS 40024 define IDM RUN __ RAND _ IR 40025 define IDM SETTING TS 25 40026 define IDM SETTING TS 15 40027 define IDM SETTING TS 5 40028 define IDM INSTRUCTION 40029 define IDM SETTING AMT 1K 40031 define IDM SETTING _AMT 5K 40032 define IDM SETTING AMT 10K 40033 define IDM SETTING AMT 50K 40034 define IDM SETTING AMT 100K 40035 define IDM SETTING AMT _250K 40036 define IDM SETTING zro 10 40037 define IDM SETTING _AMT_ 512K 40039 tdefine IDM SETTING AMT 1M 40040 define IDM SETTING AMT 5M 40041 36
31. erial correlation numbers would grow further from zero thus showing a higher degree of correlation from bit to bit Yet another possibility for the correlation is the fact that the screen resolution and therefore its binary representation is bounded Such bounds are known to provide in some cases a higher degree of correlation 2 27 The serial correlation is likely to be of greater importance to the decision of whether to use the touchscreen for a random bit sequence because it is not as dynamic as the audio can be when implemented as a driver The touchscreen could if the Original Equipment Manufacturer OEM of a Pocket PC device were to incorporate his into their native touchscreen driver collect data periodically form the screen as the device is used throughout the day However this may provide an unwanted bias in the sense that the Pocket PC invites a particular pattern of use The Start button is tapped often and the resulting pop up menu is bound to have some preferred applications i e tap points In addition the command bar and other menu items are typically restricted to the top and bottom of the display Essentially the typical use of a Pocket PC is not likely to provide a good source of randomness which means that the user will need to intervene and generate a new seed manually or when prompted to do so Either way 1s invasive and not likely to be adopted by users 5 3 Chi Square Distribution Analysi
32. ess these tests indicate that the chosen sources of randomness may be suitable for cryptographic applications which is contradictory to the findings of 1 where it is claimed that microphone input is not an adequate source of entropy on any computing system Of all the sources examined the audio source appears to be the best when tested with the ENT Test Suite In particular the 16 bit audio samples at either 8kHz or 44kHz seemed to provide the best results in most areas when raw or deskewed data was used It is expected that a dynamic pool implementation of the audio collection will provide a correction to the relatively sporadic serial correlation showing of the audio samples and that a larger ample collected as would be in a practical application would provide a better estimate of Pi via the Monte Carlo method All things considered handheld devices may possess adequate random sources for the purpose of seeding deterministic PRNGs In particular those 31 handheld devices capable of recording audio data are likely to provide a suitable means of gathering seed data 6 2 Recommendations for Future Work It can be concluded from this study that 16 bit audio samples taken at a sampling rate of 8kHz when deskewed provide the best source of randomness from those examined on the Dell Axim X5 Pocket PC handheld device Further inference of these results may be examined in future work A continuation of this work may be interested i
33. imal Compression Estimated Entropy The estimation of entropy is derived in the ENT Test Suite from the ability to compress a file optimally If the file is extremely compressible 16 then it is judged to be non random The result of this test is given as a percentage and is then used to estimate the entropy contained in each bit of the sequence A value close to 1 is desired 3 5 2 5 Serial Correlation Test The Serial Correlation Test measures the extent to which a given bit in the sequence is correlated to past or future bits in the sequence The result of this test is given on a scale from zero to one where zero indicates no detected correlation and one indicates definite correlation The results of this test will be closer to zero for sequences that approach true randomness Further description of this test can be found in 7 3 6 Quantity of Collected Data Approximately 1MB of data was collected for each source configuration Randomness was then collected from these files using the colent command After randomness was collected this new data set was deskewed using the deskew command This process resulted in a file significantly smaller in size than the raw data file The smallest file size after full distillation was just over 15KB so all of the files used for testing were truncated using the truncfile command to 15 360 bytes 122 880 bits As is evident from the data quantity reduction due to the distillation process
34. intf Starting process n endif while 1 count 0 ifdef DEBUG printf Reading Input file s inFilePath tendif do count read inFile temp 1 Read one byte from the file if count 0 If byte not read or error then i set EOF flag to indicate such eofFlag 1 ifdef DEBUG printf count EOF n tendif tifdef VERBOSE DEBUG printf readBuffer d being assigned n i endif if eofFlag If EOF flag is set then break out break of the loop prior to writing readBuffer i temp 0 itt while i MAX DESKEW BUFFER SIZE count i ifdef DEBUG printf d bytes read so far to output file n count tendif for i O i lt c fOf 7 a readBuffer i b readBuffer il I b is zero or if a is e then we have different b entropy if zero then the bit was set and lsb of writeBufferfidx otherwise buffer remains unchanged 0x1 bits have been packed into have been through to 6 then the index is place Otherwise packCount variable is reset 63 writing ount i 3 gt 1 Jj 2 maskArray j amp maskArray 3j 1 amp f a is not equal to Zero and qual to zero and b is not its and should collect the a amp amp b I ta amp amp b If a is not equal to a 1l is written to the and the a is zero if a writeBuffer idx Keep track of how many
35. irst prepared then registered with the audio device A function is invoked to start recording and will record continuously thus filling the buffer When the buffer has been filled a message is sent to the recording entity at which time the recording can be stopped the buffer unprepared 1 e unregistered and then used The use of the WAV file format is beneficial in the sense that the WAV specification does not call for compression of the audio samples 1 such compression or other manipulation would not provide suitable access to the samples 11 A practical implementation of an audio based source of randomness would provide a driver that is able to provide a dynamic entropy pool from which seed values can be drawn The pool would be updated periodically in order to bolster unpredictability This means that the audio device would be periodically enabled in order to record sample noises An owner of a handheld device may be in any number of places so the study sought to provide a variety of sample locations in addition to a variety of sample types However a simple continuous design was implemented for this study The sample locations chosen were riding in an automobile dining in a restaurant attending a lecture and working in a quiet office These scenarios were chosen to reflect the potential places and situations a person may find them in throughout the course of any given day Many people commute to work or otherwise us
36. message case WM INITDIALOG trying to center the About dialog if GetWindowRect hDlg amp rtl GetClientRect GetParent hDlg amp rt DlgWidth rtl right rtl left DlgHeight rtl bottom rtl top NewPosX rt right rt left DlgWidth 2 NewPosY rt bottom rt top DlgHeight 2 56 if the About box is larger than the physical screen H if NewPosX lt 0 NewPosx 0 if NewPosY lt 0 NewPosY 0 SetWindowPos hDlg 0 NewPosX NewPosY 05 0 SWP NOZORDER SWP NOSIZE return TRUE case WM COMMAND if LOWORD wParam IDOK LOWORD wParam IDCANCEL EndDialog hDlg LOWORD wParam return TRUE break return FALSE FUNCTION AudioCallback PURPOSE Receives the callback when the WAVEHDR object is full and ready to be read void AudioCallback void dataCollected TRUE SoundRecorderClose RECT rt GetClientRect g hWnd amp rt InvalidateRect g hWnd amp rt TRUE FUNCTION DoMouseMain DATE April 2003 PURPOSE Handle touchscreen events for pen tracking PARAMS i hWnd wMsg wParam lParam 57 RETURN LRESULT NOTES Adapted from code found in Douglas Boling s book Programming Microsoft Windows CE 2nd Ed ay LRESULT DoMouseMain HWND hWnd UINT wMsg WPARAM wParam LPARAM lParam POINT ptM UINT uPoints 0 HDC hdc CHAR
37. mples shows the estimation of the touchscreen samples at all levels of distillation Audio Samples Haslv Carls Caliasle n Pi 16 bit 11kHz 16 bit Z2kHz 16 bit 44kHz 16 Lit BkHz Btt 11kHz Bbt 22kHz B bit 44kHz Conf igur aiton and Distillation Figure 6 Monte Carlo Estimation of Pi for Audio Samples Touchscreen E Sre IB jOrs D 15ns Beale Carle Kulimalv n Pi Distillation Figure 7 Monte Carlo Estimation of Pi for Touchscreen Samples 22 4 4 Serial Correlation These are the results of the ENT Serial Correlation Test Recall that a value close to 0 0 is desired for a random sequence Figure 8 Serial Correlation of Audio Samples shows the serial correlation of the audio samples at all levels of distillation and Figure 9 Serial Correlation of Touchscreen Samples shows the serial correlation of the touchscreen samples at all levels of distillation Audio Samples mca Wi Ciass oom Dati O Restaur ant Serial Curervlalina Conf igur ation and Distillation Figure 8 Serial Correlation of Audio Samples Touchscreen Serial Currvrlalins Distillation Figure 9 Serial Correlation of Touchscreen Samples 23 Figure 8 Serial Correlation of Audio Samples is somewhat difficult to interpret so Figure 10 Average Serial Correlation of Audio Samples shows the average estimation of all audio sample configurations i e and rate at all levels of distillation Average of Au
38. n LPTSTR void PackSeedData 23 DWORD WINAPI lpData int WINAPI WinMain AudioPowerManageSubversion LPVOID HINSTANCE hInstance HINSTANCE hPrevinstance LPTSTR lpCmdLine int nCmdShow MSG msg HACCEL hAccelTable Perform application initialization if tInitInstance hInstance nCmdShow return FALSE 48 hAccelTable LoadAccelerators hInstance LPCTSTR IDC AUDIO Main message loop while GetMessage amp msg NULL 0 0 if TranslateAccelerator msg hwnd hAccelTable amp msg TranslateMessage amp msg DispatchMessage amp msg return msg wParam 4 FUNCTION MyRegisterClass PURPOSE Registers the window class COMMENTS It is important to call this function so that the application i will get well formed small icons associated with it 4 ATOM MyRegisterClass HINSTANCE hInstance LPTSTR szWindowClass WNDCLASS WC wc style CS HREDRAW CS VREDRAW wc lpfnWndProc WNDPROC WndProc wc cbClsExtra 0 i wc cbWndExtra 0 wc hInstance hInstance wc hIcon LoadIcon hInstance MAKEINTRESOURCE FDI AUDIO wc hCursor QO wc hbrBackground HBRUSH GetStockObject WHITE BRUSH wc lpszMenuName 0 wc lpszClassName SzWindowClass return RegisterClass amp wc FUNCTION InitInstance HANDLE int 49 PURPOSE Saves instance handle and creates main window COMMENTS
39. n a more practical implementation of an audio RNG system with emphasis placed on audio sources with additional more stringent testing Further future work should be interested in performing identical tests across multiple devices Currently the results are only applicable to a Dell Axim X5 The 16 bit audio samples at 8kHz and 44kHz sample rates performed well against the Arithmetic Mean Estimated Entropy and the Chi Square tests These samples performed only marginally well against the Monte Carlo Estimate of Pi and did not fair well at all against the Serial Correlation Test It is recommended that further study be performed in the area of attempting to massage better Serial Correlation results by using a more practical implementation and by using a larger amount of data 32 REFERENCES 1 Giles Cotter Generation of pseudorandom numbers from microphone input in computer devices March 2002 2 J Schiller D Eastlake S Crocker Randomness recommendations for security Technical report Internet Engineering Task Force December 1994 3 http www fourmilab ch random 2003 A search for ENT random on Google will turn up more references to the same content than that which is listed here 4 Dieter Gollmann Computer Security John Wiley and Sons Inc 1999 5 Intel Corporation Intel XScale Core Developer s Manual December 2000 6 Intel Corporation Intel StrongARM SA 1100 Microprocessor Developer s
40. ng As with the audio Samples the touchscreen sampling performed well at all sample resolutions but the 15ms resolution proved to be superior in most cases In all cases the deskewed or raw touchscreen data samples appeared to yield the best test results with the deskewed samples showing slightly better results in all but the Serial Correlation Test Unfortunately the only touchscreen samples that passed the Serial Correlation Test according to 26 the range given in 7 were the raw samples collected at all resolutions A potential reason for this deviance may be due to the implementation of the touchscreen collection algorithm The touchscreen resolution on a Pocket PC device is 240 x 320 and the coordinate system on the Pocket PC is such that the x and y coordinate values are placed into 16 bit WORDs This is necessary because of the range on the y axis 320 The collection method given in 3 3 1 1 1 provides for an 8 bit collection result which means that the collection will represent a maximum of 256 values for the y axis The consequence of this implementation is that those y values that range from 256 to 339 are mapped to the first 64 values of the y axis Another possibility for the correlation of the touchscreen sampling may lie in the fact that a user supplied the input If at some point during the data collection the user interacting with the program began scribbling in a patterned way then it may be the case that the s
41. nt data at intervals of approximately 5ms 10ms or 15ms The coordinates are passed as a single 32 bit value a DWORD in Microsoft parlance where the lower 16 bits represent the x coordinate and the higher 16 bits represent the y coordinate Each 16 bit value is known as a WORD The program responsible for collecting entropy represents the collected point data as the exclusive or of the low half of the x WORD with the low half of the y WORD Let the collected point data be represented by P then P LO coord 8 Hl coord A 0x00FF From this point forward any reference to screen dimension will be in the unit of pixels 10 The coord value in the previous equation is the value collected when either of the stylus generated messages are received The HI and LO functions return the high WORD and low WORD respectively and their results are then XOR d before being AND ed with a mask designed to collect only the lower eight bits of the representation Therefore the point representation used in collecting data from the touchscreen in this study is an 8 bit representation rooted in the x and y coordinates of the original touchscreen event 3 4 Audio Data Collection The Pocket PC has a rich audio interface The Pocket PC Wave API was used to prepare the audio input device collect the audio data and release the audio input device appropriately This method of audio recording requires the use of data buffers A buffer of bytes is f
42. ot apply for obvious reasons Those that do apply are the hardware based methods and the mouse based method The keyboard timing method cannot 6 be guaranteed across platforms to be non buffered and the software based methods with the exception of coordinate based mouse samples are all deterministic in nature This shortens the list of potential sources of randomness to e Mouse movements e Audio video input e Hardware noise 2 2 Handheld Devices There are many handheld devices on the market today Some are extremely specialized and used for rugged outdoor activity and others are designed for executives knowledge workers and others who need more than simple personal information management Still other handheld devices are simple managers of information that keep track of dates schedules and the like It can be argued however that there are two top handheld devices in the United States of America e Palm based platforms e Microsoft Pocket PC based platforms These handhelds are designed with a variety of microprocessors at their core It appears to be the case however that the Palm based platforms are primarily designed around Motorola DragonBall microprocessors and that 7 the Microsoft based platforms are primarily designed around Intel microprocessors including the SA11xx SA111x series and the XScale processors 3 Materials and Methods 3 1 The Seed Goal It was established in Section 2 that the t
43. quare Distribution Percentage 5 18 8 car 168 44 car 18 8 classroom 16 44 classroom 16 8 office 16 44 office 16 8 restaurant 16 44 restaurant Source Configuration Figure 12 Chi Square Test Results for 16 Bit Audio Samples DESKEWED As is clearly evident in Figure 11 and Figure 12 the deskewed 16 bit audio samples taken at a rate of SkHz provide the most satisfactory results when the Chi Squared Distribution is utilized Out of eight sample configurations the two that were most unacceptable came from 16 bit 44kHz samples in the classroom and office The only time the 44kHz samples faired better than the 8kHz samples was in the restaurant location Otherwise the 16 bit SKHz samples were consistently near 5096 and therefore performed very well against the Chi Squared Distribution test 6 Conclusion The results of this study are both promising and concerning On some levels the results appear to be promising and should elicit further study in 30 these areas On other levels the results seemed to warrant that the research direction should be altered to other potential sources of randomness 6 1 General Conclusions As mentioned in Section 4 the touchscreen and audio implementations were not ideal and even though the samples appear promising for the purpose of random number generation the implementation issues should be fixed and the data resampled and retested prior to further exploration of the subject Nonethel
44. rid cryptosystems The Advanced Encryption Standard AES Data Encryption Standard DES and RSA among others require randomly generated data 15 13 14 10 11 17 Authentication Systems Some authentication systems require random data as well An example of such a scheme is the Unix method of password storage which may require a salt value to store a password in order to prevent identical passwords from appearing identical in the password storage file 4 Dieter Gollmann in his book Computer Security is concerned about the layer below when designing and evaluating computer security systems 4 His basic concern is that the foundation upon which security measures are constructed should be at least as secure as the application being implemented If the foundation is flawed then the security built upon that 3 foundation is flawed The same reasoning can be applied to cryptographic applications and pseudo random number generation The generation of random data is a layer below relative to a cryptosystem For example a PRNG responsible for generating AES keys is the layer below relative to the AES implementation The PRNG itself has a layer below known as the seed The seed is that value which is used to start pseudo random number generation and should be acquired from a random source According to NIST all true randomness is confined to seed generation 12 As long as the seed is not known to
45. rue source of security for a given accepted PRNG lies in the seeding of that PRNG Because the focus is upon the seed there are slightly different randomness requirements Though the output of seed and pseudo random number generators must be unpredictable the seed generator need not be capable of generating very long random bit sequences The sequences generated should pass as many randomness tests as possible however shorter sequences can be tested 3 2 Random Bit Collection Source The purpose of this research is to study some of the potentially random sources that may be available in a handheld device Although there are several potential sources of randomness in handheld devices only two were chosen for this study audio input and touchscreen input A brief review of the datasheets user manuals for the DragonBall XScale and SA1110 microprocessors reveal that there are no RNGs made available to the systems designed around them 6 5 9 3 3 Handheld Implementation Platform There are many handheld devices available today but one of the more popular platforms was chosen for this study the Microsoft Pocket PC The Pocket PC operating system runs on several different handheld devices all with different configurations However all Pocket PC devices are required by Microsoft to meet certain specifications As a result of this mandate all Pocket PC devices can be expected to have a common denominator of hardware and fun
46. s Because the Chi Square Distribution is perhaps the most sensitive test in the ENT Test Suite it has been given special consideration in this discussion The results have thus far indicated that 16 bit audio samples taken at either 8kHz or 44kHz rates yield the best random data in this study when serial correlation is not considered Moreover the deskewed and raw 28 samples provided the best random data out of all the 16 bit 8 44kHz samples F ni 11 Chi Square Test Results for 16 Bit Audio Samples RAW shows the percentage of the time that raw audio samples of the given configuration will exceed the Chi Square Distribution value Recall that very high or very low percentages are concluded to be non random and that the closer to 50 the percentage is the more likely it is that the sequence under test is random 3 7 16 Bit Audio Samples at 8kHz and 44kHz RAW 60 00 50 00 40 00 E 20 00 16 8 car 16 44 car 16 8 d asst oom 16 44 cd aesr oom 16 8 of fice 16 44 df fice 16 8 r estau ant 16 44 r estau ant Sour ce Configuration Figure 11 Chi Square Test Results for 16 Bit Audio Samples RAW Similarly Figure 12 Chi Square Test Results for 16 Bit Audio Samples DESKEWED shows the percentage of the time that the deskewed audio samples of the given configuration will exceed the Chi Square Distribution value 29 16 Bit Audio Samples at 8kHz and 44kHz DESKEWED 50 00 F Chi S
47. settings for your capture method from the Settings menu DrawText hdc szOut tcslen szOut rt DT LEFT DT WORDBREAK rt top rt top 15 Swprintf szOut TEXT then select the desired capture method from the Run menu DrawText hdc szOut _teslen szOut amp rt DT LEFT DT WORDBREAK OS COLLECTION IS RUNNING else if running OS if dataCollected swprintf szOut TEXT Collecting data from OS DrawText hdc szOut tcslen szOut amp rt DT LEFT DT WORDBREAK OsRandInitialize outFileName 0 dataCollectionAmount OsRandStart dataCollected TRUE InvalidateRect g hWnd amp rt TRUE 7 else OsRandClose swprintf szOut TEXT Data from OS has been collected DrawText hdc szOut tcslen szOut amp rt DT LEFT DT WORDBREAK IR COLLECTION IS RUNNING else if running IR if dataCollected Swprintf szOut TEXT Collecting data from IR device DrawText hdc szOut _tcslen szOut amp rt DT LEFT DT WORDBREAK IrRandInitialize outFileName dataCollectionAmount DWORD LoggerFunction IrRandStart 54 dataCollected TRUE InvalidateRect g_ hWnd amp rt TRUE else IrRandClose swprintf szOut TEXT IR data has been collected DrawText hdc szOut _tcslen szOut amp rt DT LEFT DT WORDBREAK TS COLLECTION IS RUNNING else if running TRACK if dataCollected if d
48. sts mathematically but to describe their general operation and to provide proper methods of result interpretation moreover much of the information has been adapted from 3 Much of the information contained in the test description sections was adapted from 3 except where otherwise noted 15 random if the given percentage lies between 95 and 99 and if the given percentage lies between 1 and 5 Percentages between 90 and 95 and between 5 and 10 are almost suspect 7 If the percentage given does not fall into any of these ranges then the sequence can be judged as random 3 5 2 2 Arithmetic Mean Test The Arithmetic Mean Test takes the sum of the bits contained in the sequence then divides the sum by the length of the sequence This is in effect a frequency test that indicates how many ones and zeros exist in the given sequence For bit sequences the closer the result of this test comes to 0 5 the more likely it is that the given sequence is random 3 5 2 3 Monte Carlo Estimation of Pi The Monte Carlo Estimation of Pi is a test that first gathers the bits of the sequence into bytes The bytes are then interpreted as successive 24 bit coordinates within a square If the point falls within a circle inscribed in the square than that point is registered as a hit The hits falling within the circle are then used to estimate the area of the circle from which the estimation of Pi is derived 3 5 2 4 Opt
49. tatistics The first item under software based generators is not in the author s opinion properly categorized In effect gathering information from the 5 keyboard mouse of a given system is gathering from an external source rather than from an internal source However there are some caveats associated with such input which is likely why it has been categorized in such a manner A common approach to collecting random samples is to gather the timing differences between keystrokes and or mouse movements However 2 has pointed out that many keyboard and mouse inputs are buffered and will therefore not yield proper timing results However mouse movements need not be timed Rather the coordinate system can be utilized to produce random values Using the system clock as a seed source for a PRNG is often a tactic that is used but not one that should be used for any situation in which an adversary is interested in the value of the seed As 2 points out clocks and timers in computer systems vary widely in terms of resolution and the timing of the code execution may alter the perception of the true timing of the clock A similar argument can be made against VO buffer content which may under a denial of service attack be well known or easily guessable Effectively these methods of seeding a PRNG which is deterministic use deterministically generated seed values When considering PRNG seed sources some of the random sources do n
50. te back to this component and then prints on the screen PARAMS message a pointer to the message null term string RETURN NONE xf void LoggerFunction LPTSTR message swprintf errorMessage message errorPresent TRUE RECT rt GetClientRect g hWnd amp rt InvalidateRect g hWnd amp rt TRUE DWORD WINAPI AudioPowerManageSubversion LPVOID lpData while dataCollected SystemIdleTimerReset Sleep 2000 return ERROR SUCCESS Linux Source Deskew c DESKEW C AUTHOR A W Montville VERSION 1 0 oF X Given an input file which has entropy bits collected i e the lowest s bit from collected raw bytes the output file will contain deskewed information R The input data read from the input file supplied at the command line is parsed in bit pairs starting with the first byte of the file and moving toward the last byte of the file The first bit of the pair a is compared to the 60 second bit of the pair b If they are the same both bits are discarded and il the algorithm moves on to the next bit pair If they are different then the b bit a is kept as the output bit of the generator which produced the input data This method is described in Handbook of Applied Cryptography by A Menezes et al see page 173 Copyright c 2003 A W Montville 4 include lt fcntl h gt include lt stdio h gt include lt stdlib h gt
51. the character If we the last shift takes incremented and the if packCount lt 7 packCount writeBuffer idx lt lt else packCount idx 0 write outFile writeBuffer idx 1 if eofFlag break close inFile close outFile else DeskewUsage return 0 void DeskewUsage printf n n pPrintf 77 USAGE 3n 9 printtf deskew lt infile gt lt outfile gt n printi NaN collect entropy c xk COLLECT ENTROPY C AUTHOR A W Montville VERSION 1 0 X Given an input file this creates an output file containing 1 bit of data for every 8 bits collected The least significant bit is collected Copyright c 2003 A W Montville a7 include fcntl h include lt stdio h gt include lt stdlib h gt include lt sys stat h gt include lt sys types h gt 65 include lt unistd h gt void CollectEntropyUsage void int main int argc char argv char inFilePath argv 1 char outFilePath argv 2 char temp 1 char toWrite 1 mode t mode int inFile outFile int count 0 char mask 0x0001 Check that enough arguments were supplied otherwise print usage if argc gt 3 mode S_IRUSR S_IWUSR S IRGRP S IWGRP S IROTH inFile open inFilePath O RDONLY mode outFile open outFilePath O WRONLY O EXCL O CREAT mode if inFile 1 perror inFil
52. tically generated random data is not typically referred to as random but as pseudo random 7 A generator producing pseudo random data is referred to as a Pseudo Random Number Generator PRNG whereas a generator producing natural random numbers is referred to as a Random Number Generator RNG Oddly enough sequences generated by a PRNG often appear to be more random than those generated from naturally occurring sources 12 A brief review of some cryptographic application specifications demonstrates the reliance upon random data In the context of this paper the term random will always refer to a natural or physical source of randomness and the term pseudo random will always refer to a deterministic source of randomness in a similar manner when a RNG is discussed it will be in the context of natural or physical randomness and when a PRNG is discussed it will be in the context of a deterministic method of randomness generation 2 Network Protocols Some network protocols require what is known as a nonce a number that is used once and further require that such numbers are random the ClientHello and ServerHello messages of the SSL TLS network protocols require randomly generated data which eventually become the keys used to encrypt the session 16 Cryptosystems Virtually all cryptosystems require random data for the purpose of key generation This is true when examining public key private key or hyb
53. user specified size All of these Linux based command line tools were implemented using the C programming language For more information regarding the implementation of these tools see the Appendix 3 5 Test Method Raw data was collected from each of the data sources touchscreen and audio input The collected data was logged and filed prior to distillation The distillation process performed as many as two steps which were designed 13 to do two things collect randomness from the data and to deskew remove bias from the data Randomness was collected by taking the least significant bit of every byte collected and deskewing was performed by the method listed in Section 3 5 1 The collected data was distilled into four distinct categories e Raw Data the uncorrected data e Entropy Data raw data that has been distilled for randomness e Deskewed Data raw data that has been distilled for bias correction and e Entropy and Deskewed Data entropy data that has been distilled for bias correction 3 5 1 Deskewing To Remove Bias The deskewing method used in mentioned in 13 and 8 This distillation process is necessary because the generator may provide a sequence that contains a greater number of ones or zeros in the bit seguence The method of deskewing data is to look at the bits in a sequence in bit pairs t and f for all i from i 3 5 n If t and f are equal discard the bits and move on to the
Download Pdf Manuals
Related Search