- cypherpunks - lists.cpunks.org

Arithmetic Coding and Blinding for Lattice Cryptography
by coderman 14 Mar '16

14 Mar '16

https://eprint.iacr.org/2016/276 Abstract: In this work we apply information theoretically optimal arithmetic coding and a number of novel side-channel blinding countermeasure techniques to create BLZZRD, a practical, compact, and more quantum-resistant variant of the BLISS Ring-LWE Signature Scheme. We show how the hash-based random oracle can be modified to be more secure against quantum preimage attacks while decreasing signature size at any given security level. Most lattice-based cryptographic algorithms require non-uniformly distributed ciphertext, signature, and public/private key data to be stored and transmitted; hence there is a requirement for compression. Arithmetic Coding offers an information theoretically optimal compression for stationary and memoryless sources, such as the discrete Gaussian distributions often used in Lattice-based cryptography. We show that this technique gives better signature sizes than the previously proposed advanced Huffman-based compressors. We further demonstrate that arithmetic decoding from an uniform source to target distribution is also an optimal Gaussian sampling method in the sense that a minimal amount of true random bits is required. Performance of the new Binary Arithmetic Coding (BAC) sampler is comparable to other mainstream samplers. The same code, tables, or circuitry can be utilised for both tasks, eliminating the need for separate sampling and compression components. We also describe a simple blinding technique that can be applied to anti-cyclic polynomial multiplication to mask timing- and power consumption side-channels in ring arithmetic. We further show that Gaussian sampling can also be blinded by a split-and-permute technique while reducing the size of required CDF tables.

2 1

Mathematicians Discover Prime Conspiracy
by coderman 14 Mar '16

14 Mar '16

Mathematicians Discover Prime Conspiracy A previously unnoticed property of prime numbers seems to violate a longstanding assumption about how they behave. By: Erica Klarreich March 13, 2016 Two mathematicians have uncovered a simple, previously unnoticed property of prime numbers — those numbers that are divisible only by 1 and themselves. Prime numbers, it seems, have decided preferences about the final digits of the primes that immediately follow them. Among the first billion prime numbers, for instance, a prime ending in 9 is almost 65 percent more likely to be followed by a prime ending in 1 than another prime ending in 9. In a paper posted online today, Kannan Soundararajan and Robert Lemke Oliver of Stanford University present both numerical and theoretical evidence that prime numbers repel other would-be primes that end in the same digit, and have varied predilections for being followed by primes ending in the other possible final digits. “We’ve been studying primes for a long time, and no one spotted this before,” said Andrew Granville, a number theorist at the University of Montreal and University College London. “It’s crazy.” The discovery is the exact opposite of what most mathematicians would have predicted, said Ken Ono, a number theorist at Emory University in Atlanta. When he first heard the news, he said, “I was floored. I thought, ‘For sure, your program’s not working.’” This conspiracy among prime numbers seems, at first glance, to violate a longstanding assumption in number theory: that prime numbers behave much like random numbers. Most mathematicians would have assumed, Granville and Ono agreed, that a prime should have an equal chance of being followed by a prime ending in 1, 3, 7 or 9 (the four possible endings for all prime numbers except 2 and 5). “I can’t believe anyone in the world would have guessed this,” Granville said. Even after having seen Lemke Oliver and Soundararajan’s analysis of their phenomenon, he said, “it still seems like a strange thing.” Yet the pair’s work doesn’t upend the notion that primes behave randomly so much as point to how subtle their particular mix of randomness and order is. “Can we redefine what ‘random’ means in this context so that once again, [this phenomenon] looks like it might be random?” Soundararajan said. “That’s what we think we’ve done.” Prime Preferences Soundararajan was drawn to study consecutive primes after hearing a lecture at Stanford by the mathematician Tadashi Tokieda, of the University of Cambridge, in which he mentioned a counterintuitive property of coin-tossing: If Alice tosses a coin until she sees a head followed by a tail, and Bob tosses a coin until he sees two heads in a row, then on average, Alice will require four tosses while Bob will require six tosses (try this at home!), even though head-tail and head-head have an equal chance of appearing after two coin tosses. Soundararajan wondered if similarly strange phenomena appear in other contexts. Since he has studied the primes for decades, he turned to them — and found something even stranger than he had bargained for. Looking at prime numbers written in base 3 — in which roughly half the primes end in 1 and half end in 2 — he found that among primes smaller than 1,000, a prime ending in 1 is more than twice as likely to be followed by a prime ending in 2 than by another prime ending in 1. Likewise, a prime ending in 2 prefers to be followed a prime ending in 1. Soundararajan showed his findings to postdoctoral researcher Lemke Oliver, who was shocked. He immediately wrote a program that searched much farther out along the number line — through the first 400 billion primes. Lemke Oliver again found that primes seem to avoid being followed by another prime with the same final digit. The primes “really hate to repeat themselves,” Lemke Oliver said. Lemke Oliver and Soundararajan discovered that this sort of bias in the final digits of consecutive primes holds not just in base 3, but also in base 10 and several other bases; they conjecture that it’s true in every base. The biases that they found appear to even out, little by little, as you go farther along the number line — but they do so at a snail’s pace. “It’s the rate at which they even out which is surprising to me,” said James Maynard, a number theorist at the University of Oxford. When Soundararajan first told Maynard what the pair had discovered, “I only half believed him,” Maynard said. “As soon as I went back to my office, I ran a numerical experiment to check this myself.” Lemke Oliver and Soundararajan’s first guess for why this bias occurs was a simple one: Maybe a prime ending in 3, say, is more likely to be followed by a prime ending in 7, 9 or 1 merely because it encounters numbers with those endings before it reaches another number ending in 3. For example, 43 is followed by 47, 49 and 51 before it hits 53, and one of those numbers, 47, is prime. But the pair of mathematicians soon realized that this potential explanation couldn’t account for the magnitude of the biases they found. Nor could it explain why, as the pair found, primes ending in 3 seem to like being followed by primes ending in 9 more than 1 or 7. To explain these and other preferences, Lemke Oliver and Soundararajan had to delve into the deepest model mathematicians have for random behavior in the primes. Random Primes Prime numbers, of course, are not really random at all — they are completely determined. Yet in many respects, they seem to behave like a list of random numbers, governed by just one overarching rule: The approximate density of primes near any number is inversely proportional to how many digits the number has. In 1936, Swedish mathematician Harald Cramér explored this idea using an elementary model for generating random prime-like numbers: At every whole number, flip a weighted coin — weighted by the prime density near that number — to decide whether to include that number in your list of random “primes.” Cramér showed that this coin-tossing model does an excellent job of predicting certain features of the real primes, such as how many to expect between two consecutive perfect squares. Despite its predictive power, Cramér’s model is a vast oversimplification. For instance, even numbers have as good a chance of being chosen as odd numbers, whereas real primes are never even, apart from the number 2. Over the years, mathematicians have developed refinements of Cramér’s model that, for instance, bar even numbers and numbers divisible by 3, 5, and other small primes. These simple coin-tossing models tend to be very useful rules of thumb about how prime numbers behave. They accurately predict, among other things, that prime numbers shouldn’t care what their final digit is — and indeed, primes ending in 1, 3, 7 and 9 occur with roughly equal frequency. Yet similar logic seems to suggest that primes shouldn’t care what digit the prime after them ends in. It was probably mathematicians’ overreliance on the simple coin-tossing heuristics that made them miss the biases in consecutive primes for so long, Granville said. “It’s easy to take too much for granted — to assume that your first guess is true.” The primes’ preferences about the final digits of the primes that follow them can be explained, Soundararajan and Lemke Oliver found, using a much more refined model of randomness in primes, something called the prime k-tuples conjecture. Originally stated by mathematicians G. H. Hardy and J. E. Littlewood in 1923, the conjecture provides precise estimates of how often every possible constellation of primes with a given spacing pattern will appear. A wealth of numerical evidence supports the conjecture, but so far a proof has eluded mathematicians. The prime k-tuples conjecture subsumes many of the most central open problems in prime numbers, such as the twin primes conjecture, which posits that there are infinitely many pairs of primes — such as 17 and 19 — that are only two apart. Most mathematicians believe the twin primes conjecture not so much because they keep finding more twin primes, Maynard said, but because the number of twin primes they’ve found fits so neatly with what the prime k-tuples conjecture predicts. In a similar way, Soundararajan and Lemke Oliver have found that the biases they uncovered in consecutive primes come very close to what the prime k-tuples conjecture predicts. In other words, the most sophisticated conjecture mathematicians have about randomness in primes forces the primes to display strong biases. “I have to rethink how I teach my class in analytic number theory now,” Ono said. At this early stage, mathematicians say, it’s hard to know whether these biases are isolated peculiarities, or whether they have deep connections to other mathematical structures in the primes or elsewhere. Ono predicts, however, that mathematicians will immediately start looking for similar biases in related contexts, such as prime polynomials — fundamental objects in number theory that can’t be factored into simpler polynomials. And the finding will make mathematicians look at the primes themselves with fresh eyes, Granville said. “You could wonder, what else have we missed about the primes?” --- https://www.quantamagazine.org/20160313-mathematicians-discover-prime-consp…

2 1

Apple in EDNY added as interested party in another iPhone case in EDNY
by John Young 13 Mar '16

13 Mar '16

Apple in EDNY added as interested party in another iPhone case in EDNY https://cryptome.org/2016/03/usg-apple-feng-edny-144.pdf (151 pp, 10MB) Magistrate Judge James Orenstein: The Clerk of Court shall add Apple Inc. as an interested party in United States v. Feng. All documents must be filed on both dockets. (Brodie, Margo) (Entered: 03/12/2016)

1 0

[OT] Would someone please check if links2 and elinks verify certificates on clean install of Debian 8?
by Georgi Guninski 13 Mar '16

13 Mar '16

Apologies for offtopic (this might be mildly ontopic about the current state of crypto in open source). Would someone please check if links2 and elinks verify certificates on fresh install of Debian 8? To verify, try to open site which doesn't properly chain to trusted root, say https://cacert.org (unless you trust their root ) and check if it opens or there is error/warning. For me, on updated system, both don't verify certificates. Looks like at least ubuntu and fedora killed the elinks bug long ago. Searching the web for "$browser self signed certificate" shows some relevant results.

2 2

Re: participation in sensor networks
by Georgi Guninski 13 Mar '16

13 Mar '16

On Sat, Mar 12, 2016 at 05:13:28PM -0500, dan(a)geer.org wrote: > Georgi Guninski writes: > | On Thu, Mar 03, 2016 at 08:34:14AM -0500, dan(a)geer.org wrote: > | > The question here is perhaps obvious: Will you opt out and suffer > | > the consequences thereof? > | > > | > --dan > | > | Let me counter-ask only `dan': > | > | Will you exchange a walk on part in a war for > | a lead role in a cage? > | > | This is not exactly quote from Floyd's song. > > > After looking up the lyrics and reading a few pages about them, > I confess to still being confused as to what they mean and, hence, > what their question is. That is an honest answer -- I am not good > (at all) with anything that is "high art" or whatever the right > terminology here would be. > > Now, as a guess, I'll counter by asking if the lyric is simply a > light modernization of: > > I must study politics and war, that my sons may have the liberty > to study mathematics and philosophy, natural history and naval > architecture, in order to give their children a right to study > painting, poetry, music, architecture, tapestry, and porcelain. > -- John Adams, 2nd US President > > If the "Floyd" lyric asks whether yours is a purpose-driven life, > then my answer to "freedom, security, comfort, choose two" is freedom > and security, abjuring comfort, per se. > > Never mind the lyrics, assume it doesn't exist. Assuming you are the same dan geer who is some boss at in-q-tel, which appears closely related to the cia, what is your definition of "freedom" -- what the usgov decides to give to the enslaved peasants?

1 0

Foreign Intelligence Relations Management System (FIRMS)
by Michael Best 13 Mar '16

13 Mar '16

Anyone heard of Foreign Intelligence Relations Management System (FIRMS)? All I can dig up ATM is the abbreviation itself. Not sure if it's State, CIA, or etc. jurisdiction -- Veritas aequitas liberabit vos Veri universum vici That 1 Archive <http://that1archive.neocities.org/> @NatSecGeek <https://twitter.com/NatSecGeek> -----BEGIN PGP PUBLIC KEY BLOCK----- Version: SKS 1.1.5 Comment: Hostname: pgp.mit.edu mQINBChG9zoBEADKzALG4UHCjY6L9OFUxWRVGGCW7LY71K2EAK/0jkRh1wPkJ4chPaVJ3vVD nJ0d8HxsyR5R3+y7GH6GCc/tK0IDPJah+xpQnraS1nWUvAlSaaxsBK4hJfuVGyfBg/joQVKU OhpqJLQhRIkUWk30QC94IbOKiCTb6V4pStLYyrLieewjT481vvRIYp/48IS5eiveZW0/IpcA HBON7xJw6P1murC8PNOJSWRCp9FJhcs3wIPG3cFTfsxSZnGcoivMgFLtGAfLbztpZkcHEMOR 4qamVvirzYGHma0UlOzyNr7xpxyLXFsU5kKzQ8Az2nP1GG7vuqXSjPNLIvvHFL+g+gKuCe9W xTa9Ac038RRSiBGdDrvTFpQ/h9h5GWIHP7nsA4TCeZSpL81aqp7Cb0MK3KPQmteTPIujVCnx jXXHrOe9Tj6iYUU8edApISyBEVFZMd+EtfDEDf/ZwDjzSGE85vv1dZ/ck7iJvS8FwM8hsRBG U9huCKiItGs26teUJ2Sum49YaEiDL4QLQhJ+FbsAusxJg+V3GE/4w75K/6/czT0p10Mf66Uo fRFTvYRE7S6CNDxzTI4q7+pnRlxMBduGC33KY4eq4Py/O3LWHBDxZ+LffIa/tWcB/7oZ6yDo bdWleNk5wnJdPGr6lUTHTM4tpDIEcXYpvjzyLcMtg4tFm/Dc0QARAQABtGVNaWNoYWVsIEJl c3QgKFByaXZhdGUsIG5vdCBzZWN1cmUuIEZvciBzZWN1cmUgZW1haWwsIHJlcXVlc3QgYSBv bmUtdGltZSBrZXkuKSA8dGhlbWlrZWJlc3RAZ21haWwuY29tPokCPQQTAQoAJwUCKEb3OgIb AwUJNXc1AAULCQgHAwUVCgkICwUWAgMBAAIeAQIXgAAKCRCiYH9hY4dAS3e+D/sFwyJER4/4 ZnHYC/1EzCpHeDikSmULEgsvNgzo73thOV9/Q2I8mCJTlQjsK4rZ2YiDzi4b0CN8kzjpxtVz BsBsxfyPLrdH4VoqeqeBVzbwHxSk7bYUI3vFt+e3gBgpAxbVfPXCnYUnWPRlr9dc/JZoPJH4 p8yRIqktehbAE3Fa3gkfrXJ5e6+/nKlQhikyvo9VuErrLpPMXBzOq4/2LVfurkcOzlp1RBjs hWr6B98EiOXs44ZGLEkINxJiW8koFhw/WDuON8LKi/DtLiqqtBVTjrkqKCuKzSAVncGGcEVO 3Om3aOIOvG0do/wQKYXnpbeGsHwx2PGrJ7H+lb2bIb5KhbZkbG4rMTjsVnuGN+IF4BxBhmGz MYoooWy4VCLL0o8keomU8JPXt+fZDqJ9sNjY/asTsjOa6aE3bIa6w3mWUeefGwA25oXur3Rr L3wmu1pPzCejumfA1X93dS9UZS3xni+7W34g6YbsREuaZ+YBxFLN227JXAx2pEdjLsuVOaqM 9CO7ARHsxDZoE9U7n0s3txnSw/2YYwjEK1wDhdLnHBL3ZzaAcaHnpzsTYQAVW7uXKKHhzeSK GP3O4ByCisM/7WLFvIIpaNNs85jI1PvKH0GutSTl9xXDfWuYMl9rwwbteBB/oGSxlIFe0pqq IDNfAJdR/HjTLqrTES2wdXJS1bkCDQQoRvc6ARAAmltXrhVfpePdIFrfEHCet4nkQvmRI+AX rUgiNlxQDW8M5FzlUfT2xpMXHMWuKehTYpFq7bNbFi+fwBhMajgvgDsTuLInftKSFp+sisbR n8psv7CpGB4jp0Xd4y1Wm/HejV/kga0kcUVVetaqyzgZedn1UnccQRzDBVWW2j2ed+hi/8g0 /d7mbVG81yzJo8tLidM90xFF7JGlijm0dBAqmhD4UgkxSnJQ3PK5onqdjdbx7HkP68RrkeTQ vhWK1978qzdSl9ljJ0jLnoAaDNPs5Dj/TyYCtqoKHUqMbTwU5nIQnJG7geMeSw/7OVnKlypF Rs/JesZzMBooZTRxZJuIB/q0wOfE/MYTwGSwLs2brUwJFJ6bSYmerZ+81S8W/Y4mehJ3o6Vl SabrrVN+LlBfUuRqd5U909WECzk6HVnwnRfL07zD+1y5cLU+e4MQs2227kLriTIxtDZ/umeG hKQgNgFGTAPHJxA96xGvQ8Ovv+XEivlO0jxBNMIiopNSlMDE+k3nigWHuavt9LUUCOd45aw7 0pgKstQQgpFfVAwV98LPpUKxa61q6wQiQHAcP7YxuQG0dsr4nUq2xids5l1IpOLzZJ3nRThM k7alkljBbqphbocV3FsSXOkpcSWns94k1QGmrPzEPLF0FHFBG6whWoaoEySMkdsN1zVu4GMU o2EAEQEAAYkCJQQYAQoADwUCKEb3OgIbDAUJNXc1AAAKCRCiYH9hY4dASzTaEACKXVgc8KmZ xWyYTUQgIwrj3J/re68uIilq0iBBDocgEZZpxyf6lD1V3IKBjAPpWyYHMrrrLY64rFDR+8DE Xyhm1Wv2S6YJuWJtyAlS4bciXjJE6evirIH5GoFq++vzsufRaudAoQ56hJ0+Z3dNMMWZ6YuP zWNNL2tvpdo3Nvd8bqiADWSffFdIPv5Yj/mZsXmaDN+7iWYlAdCrubGyGzFHlCh26Ghu6SS0 /u8x1/Oi7ma7fUMFnEsFiYjwBkD3pQKK1dm7j2f1OMxi8uky8vgBgx40aeJkoUgEvIHWsCIi CWVTyfiGeWIcKbK7tYP5jsjV5fUv+TaQ1pApt++Pyop1aogfQ8icNBQQkdX6E4gNhnPOPTM8 FTl69Tq5Ori5+TM8VM0iPGiydlcAXIAD3OyR4tZM12Ga1AtppKjx31EyDB4SPzUmDWRy5WgG NRH3+RgiK/iXVcvLdFIKj3/AvctSLdbayyaFD8zrE/wcMzLfie+iE231+rG/7gmcR3H1rcYE vxvmWAPikLQKiMUpPBNSvfLPUTrwNSGiZ5ieAAPgOooc3u5nohwZmEW1pg6HirZgIAgAYuyL aLgnikwH70guiQ4Ufsih3gy0ddsUwliUTtbYQyX0OBQoTUyaiXPy0Wu2FJfsxiW8X9Lu9pIH KOwU9K76VKot+UikGqeFQsS/Ig== =M+du -----END PGP PUBLIC KEY BLOCK-----

3 2

Obama At SXSW: No On Personal Secure Crypto And Decentral Cryptocurrencies
by grarpamp 12 Mar '16

12 Mar '16

https://news.ycombinator.com/item?id=11270529 http://yro.slashdot.org/story/16/03/11/2336205/obama-government-cant-let-sm… https://www.reddit.com/r/Bitcoin/comments/4a1hcp/obama_indirectly_attacks_b… Because terrists and children of course. Typical govt drivel, strategy, and game playing position rollout timeline. Attn Peeps... ur bein 0wn3d.

1 0

Fwd: On XML - was Fwd: [Yaml-core] Next YAML: drop equality definition
by Zenaan Harkness 12 Mar '16

12 Mar '16

I only forward the last part of this email, since the rest is domain specific (YAML de/serialization minutiae). Z ---------- Forwarded message ---------- From: Zenaan Harkness <zen(a)freedbms.net> Subject: Re: [Yaml-core] Next YAML: drop equality definition On 3/10/16, Osamu TAKEUCHI <osamu(a)big.jp> wrote: ... >> One of the reason we explicitly listed the goals, >>_in order_,was to break ties when different goals >>pushed us in different directions. Order the goals >>differently, and you'll get a different spec. I think >>you would end up with JSON if you ordered them in a >>different way. Or even, god help us, XML ;-) ... > If we give up YAML, the next choice will indeed be XML. Nope. The next choice will be YAML 2. Then the next choice will be JSON 1. Then the next choice will be JSON 2. Then the next choice will be native serialization in your language of choice. Then custom binary serialization. Then a continually permutating algorithmic mixing stream, just for laughs. There are infinite alternatives to XML and if worse comes to worst, I suggest hard transcoding your data into COBOL statements and serializing those in Base63. Nowhere would one willingly choose XML. Hell, I'd choose HTML if I was ordered to use XML on a project, just to make sure the next guy who touches that code knows that the serialization format has to be changed. Manager: "Z, did you finish that, what's it called again? Yeah, the XML serialization?" Me: "Sure did! And it's Netscape 3.1 compatible too." <snigger>HTML<snigger> Manager: <used to work at Best Buy, does not understand>"Oh, cool! That's just great! I knew I'd finish on time, and I'll tell marketing our new name too, 'NewScope compatible' - has a great ring to it. Great ring! Good job Z, you'll go places you know. Go places in this world!" > Actually, my library is build to replace XML serializer > that is provided by C#. Since we want YAML to be able > to serialize both kinds of documents, we have to think > the best balance. Should be easy. Anything's more enjoyable than XML... whoops, there I go again... :)

2 2

Apple Attorneys Move to Join CA and NY Cases
by John Young 11 Mar '16

11 Mar '16

USG-Apple EDNY - Apple Attorneys Move to Join CA and NY Cases <https://t.co/dxmWKmVGBW>https://cryptome.org/2016/03/usg-apple-edny-0 31-034.pdf

1 1

Searching Places Unknown: Law Enforcement Jurisdiction on the Dark Web
by Cari Machet 11 Mar '16

11 Mar '16

Searching Places Unknown: Law Enforcement Jurisdiction on the Dark Web Ahmed Ghappour <http://t.sidekickopen45.com/e1t/c/5/f18dQhb0S7lC8dDMPbW2n0x6l2B9nMJW7t5XZs1…> UC Hastings College of the Law March 5, 2016 http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2742706 -- Cari Machet NYC 646-436-7795 carimachet(a)gmail.com AIM carismachet Syria +963-099 277 3243 Amman +962 077 636 9407 Berlin +49 152 11779219 Reykjavik +354 894 8650 Twitter: @carimachet <https://twitter.com/carimachet> 7035 690E 5E47 41D4 B0E5 B3D1 AF90 49D6 BE09 2187 Ruh-roh, this is now necessary: This email is intended only for the addressee(s) and may contain confidential information. If you are not the intended recipient, you are hereby notified that any use of this information, dissemination, distribution, or copying of this email without permission is strictly prohibited.

5 6