QUALCOMM Incorporated · NASDAQ:QCOM

QUALCOMM — Technical Presentation (February 2003)

25 slides from QUALCOMM's technical presentation, Feb 25, 2003

  1. Slide 1: Turing: a fast software stream cipher

    Turing: a fast software stream cipher Greg Rose, Phil Hawkes {ggr, phawkes}@qualcomm.com 25-Feb-03 Copyright © QUALCOMM Inc, 2002

  2. Slide 2: Disclaimer

    DISCLAIMER! •This version (1.8 of TuringRef.c) is what we expect to publish. Any changes from now on will be because someone broke it. (Note: we said that about 1.5 and 1.7 too.) •This is an experimental cipher. Turing might not be secure. We've already found two attacks (and fixed them). We're star

  3. Slide 3: Introduction

    Introduction •Stream ciphers •Design goals •Using LFSRs for cryptography •Turing •Keying •Analysis and attacks •Conclusion 25-Feb-03 Copyright© QUALCOMM Inc, 2002 slide 3

  4. Slide 4: Stream ciphers

    Stream ciphers •Very simple – generate a stream of pseudo-random bits – XOR them into the data to encrypt – XOR them again to decrypt •Some gotchas: – can’t ever reuse the same stream of bits – so some sort of facility for Initialization Vectors is important – provides privacy but not integrity / au

  5. Slide 5: Turing's Design goals

    Turing's Design goals •Mobile phones – cheap, slow, small CPUs, little memory •Encryption in software – cheaper – can be changed without retooling •Stream cipher – two-level keying structure (re-key per data frame) – stream is "seekable" with low overhead •Very fast and simple, aggressive design •Se

  6. Slide 6: Using LFSRs for Cryptography

    Using LFSRs for Cryptography •Linear Feedback Shift Registers have been intensively studied – Good and proven distribution properties – Fast •Empirical techniques thought to produce good characteristics – decimation, irregular clocking, stuttering (not used) – nonlinear function of state, or memory

  7. Slide 7: Elements in Turing

    Elements in Turing •LFSR structure based on SOBER-t32 and SNOW 2.0 •Nonlinear filter function is a keyed transformation – Based on a round of a block cipher – Blowfish/Twofish for the key-dependent s-box – SAFER for the pseudo-Hadamard diffusion function – concept spawned from Tom St Denis' tc24 25-

  8. Slide 8: LFSRs over GF(2^8)^4

    LFSRs over GF(28)4 •Elements of field are words-sized polynomials of byte-sized binary polynomials •Addition operation is XOR, ⊕ •Multiplication is poly-mod multiplication, ⊗ – only multiply by constant – use single 8->32 table lookup, shift word by 8 bits •Instead of shifting the shift register, ca

  9. Slide 9: Turing block diagram

    Turing block diagram Register Keyed block cipher round Output PHT Keyed 8x32 s-boxes PHT step five A Mix produce mixed words Mix and add B A' B' C C' D' D E' E 25-Feb-03 Copyright© QUALCOMM Inc, 2002 slide 9

  10. Slide 10: The Shift Register

    The Shift Register •Generates nearly maximal length sequence – period (2544 – 1)/5, 5 possible cycles •Recurrence: – sn+17 = sn+15 ⊕ sn+4 ⊕ y⊗ sn •Each bit position behaves as output from a 544-bit binary shift register – recurrence relation has exactly half non-zero coefficients. •Shift register is

  11. Slide 11: The Nonlinear Function

    The Nonlinear Function •Offsets are carefully chosen – feedback taps plus function inputs form “full positive difference set” •Combine 10 words of state in a key-dependent manner – mix 5 words with PHT – pass bytes through keyed 8->32 S-boxes – mix words with PHT again – step LFSR five times and add

  12. Slide 12: Pseudo-Hadamard Transform

    Pseudo-Hadamard Transform •Matrix multiply mod 232:  A  2 1 1 1 1  A   B  1 2 1 1 1  B      C  = 1 1 2 1 1  C        D  1 1 1 2 1  D   E  1 1 1 1 1  E  •Actually: – E += A + B + C + D; – A += E; B += E; C += E; D += E •Extend to n-PHT for key loading 2

  13. Slide 13: Basic S-box

    Basic S-box •Permutation •Fairly nonlinear (min nonlinearity 104) •made by: – keying RC4 with "Alan Turing" – throwing away 736 bytes – using its permutation – best observed nonlinearity in 10,000 cycles, used first one found. 25-Feb-03 Copyright© QUALCOMM Inc, 2002 slide 13

  14. Slide 14: QUT's "Q-box"

    QUT's "Q-box" •Developed by Queensland University of Technology •8->32 bit S-box •bit positions are: – Highly nonlinear (112) – Balanced – Pairwise uncorrelated 25-Feb-03 Copyright© QUALCOMM Inc, 2002 slide 14

  15. Slide 15: Keyed S-boxes

    keyed S-boxes •Push through fixed S-box multiple times: – next slide for details •four logical S-boxes, one for each byte position, due to different key material •words of key are mixed when loaded to help thwart related-key attacks. •every byte of key affects each sbox •S-boxes can be precalculated

  16. Slide 16: More on keyed S-boxes

    More on keyed S-boxes • Si(x) = Sbox[Ki,N-1 ⊕ Sbox[Ki,N-2 ⊕ … Sbox[Ki,0 ⊕ x]…]] • at each stage, XOR (Qbox[…] rotated left (i*8+j)) to temporary word – Thanks to David McGrew and Scott Fluhrer for observing that this was better mixing than the MDS matrix • Clobber the byte corresponding to the input

  17. Slide 17: Keying

    Keying •Two stage keying – secret key from 4 to 32 bytes (32 to 256 bits) – length is significant – must be multiple of 4 – requires further keying operations (eg. frame IV) •Keying process: – pass bytes through an invertible S-box construct, then words through PHT for mixing – use output in keyed S

  18. Slide 18: Initialization Vector

    Initialization Vector • mixed key material and initialisation vector are used to fill the LFSR – IV – mixed key – word made from length of key and IV (0x010203kv, where k is keylength in words, v is IV length in words) – rest of words made by recurrence of some previous words • each word is mixed th

  19. Slide 19: Polynomial details

    Polynomial details •Byte polynomial is – z8 + z6 + z3 + z2 + 1 •Word polynomial is – y4 + 0xD0.y3 + 0x2B.y2 + 0x43.y + 0x67 •LFSR polynomial is – x17 + x15 + x4 + α, where α is the polynomial "y" •"binary equivalent" polynomial has 272 out of 544 non-zero terms 25-Feb-03 Copyright© QUALCOMM Inc, 200

  20. Slide 20: Performance

    Performance •Generates 160 bits at a time •highly parallel operations •2304 bytes ROM tables, plus code – 8x8 S-box, 8x32 Q-box, 8x32 Multiplication table •Fast implementation: – 4-5 cycles per byte on newer Pentium-style machines with multiple parallel instructions – requires 4K RAM tables computed

  21. Slide 21: Security

    Security •LFSR guarantees good statistical properties input to the nonlinear function •Strength is derived from the combination of unknown input from the LFSR and keyed non- linear transformation •Either by itself is potentially weak •Each frustrates attacks on the other •If the "block cipher part"

  22. Slide 22: Numbers

    Numbers Cipher cycles/B Key IV setup tables RAM MByte/s TuringRef 149.01 477.00 4272.31 2304.00 68.00 6.04 TuringLazy 33.44 1802.70 991.80 2304.00 4164.00 26.91 TuringTab 30.06 72457.93 900.90 2304.00 4164.00 29.94 TuringFast 6.12 72417.12 882.90 2304.00 4164.00 146.95 arrsyfor 37.49 0.00 10347.42 0

  23. Slide 23: Recent attack

    Recent attack •paper at http://www.qualcomm.com.au/Turing_attack.pdf • Basically, LFSR wasn't being stepped enough • Reuse of words in final "add" phase allowed algebraic attack on LSB's • Attack very specific to Turing 1.6. • Solution: – step LFSR total 5 times between blocks – use a different full

  24. Slide 24: Conclusion

    Conclusion •Turing is not conservatively designed – I (ggr) think it may be secure, but it's clearly "close to the edge". Maybe too close. •OK for hardware implementation •Suitable for medium embedded applications •Extremely fast in software – 146MBytes/sec on 900MHz PIII laptop, 6 cycles/byte •Sour

  25. Slide 25: Stop the presses

    Stop the presses •Free licenses! – for Turing or SOBER (or future ciphers) – for any purpose – for hardware or software – for ever – our code or yours •It only took me 5 years to get management agreement… 25-Feb-03 Copyright© QUALCOMM Inc, 2002 slide 25

Qualcomm — Technical Presentation (February 2003) on 6ix