[cryptography] NSA IDA Cryptological Research Centers
The Institute for Defense Analyses, based in Alexandria, VA,
is a 50-year partner of NSA. It has two Centers for Communications
Research at Princeton, NJ, and La Jolla, CA, both doing cryptological
research for NSA:
http://www.idaccr.org/
http://www.ccrwest.org/
The latter's web site lists only this offering:
[Quote]
La Jolla Covering Repository
A (v,k,t)-covering design is a collection of k-element subsets,
called blocks, of {1,2,...,v}, such that any t-element subset is
contained in at least one block. This site contains a collection of
good (v,k,t)-coverings. Each of these coverings gives an upper bound
for the corresponding C(v,k,t), the smallest possible number of
blocks in such a covering design.
The limit for coverings is v100, k=25, and t=8 just to draw the
line somewhere. Only coverings with at most 10 blocks are given,
except for some which were grandfathered in. Some Steiner systems
(coverings in which every t-set is covered exactly once) which are
too big for the database will be included in the link below.
[Unquote]
What is covering and how does it related to cryptology?
-
Eyeballs of the two centers:
http://cryptome.org/2013-info/09/nsa-ccr/nsa-ccr.htm ___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Asynchronous forward secrecy encryption
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 24/09/13 07:52, Trevor Perrin wrote: On Mon, Sep 23, 2013 at 4:51 AM, Michael Rogers The key agreement starts with a hash commitment, followed by an exchange of ephemeral ECDH public keys. Two short authentication strings (again, six decimal digits) are derived from the shared secret; the users exchange the authentication codes verbally to complete the process. Sounds reasonable but you'll need a 3-way handshake for the short auth strings, which could be awkward in an asynchronous messaging scenario. Good point, I should've mentioned that the key exchange protocol is designed to be carried out face to face; it requires a low-latency duplex channel, such as wifi or Bluetooth. We're also planning to support introductions through mutually trusted third parties. The protocol for Alice to introduce Bob and Carol to each other will look something like this: Bob - Alice: I'd like to introduce you to Carol Bob - Carol: I'd like to introduce you to Alice Alice - Bob: OK, here's a single-use public key I just generated Carol - Bob: OK, here's a single-use public key I just generated Bob - Alice: Here's Carol's single-use public key and contact details Bob - Carol: Here's Alice's single-use public key and contact details Alice - Bob: I've deleted my private key and started key rotation Carol - Bob: I've deleted my private key and started key rotation Bob - Alice: Carol has started key rotation, you can contact her now Bob - Carol: Alice has started key rotation, you can contact her now This process requires two-way communication between Alice and Bob, and between Bob and Carol, but that communication can be asynchronous and long distance. Alice and Carol must trust Bob not to MITM the key exchange. If they ever meet face to face, they can carry out a fresh key exchange with short authentication strings to check that Bob didn't MITM them. Cheers, Michael -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJSSE3/AAoJEBEET9GfxSfMo7MIAKeQDFLChMyKBBuzmSq29/Wc rI5HXiCD6CoPj6AU+TrFlpl+WknM/PlqTtYR1RXxmE2uDKyTUij5+ntZhvLg70uG 9D64bAW8gZ41T+MIMp1+7e55XYQt2+WcZen7Cmk78PFuMvexqtOI8OZShfqKYm/y rwpn5YfC7qV5mqJRM90PfwmEKgoom4mzl0VBw39SMjtXA1vHd4bEBseiAcp3d0h4 momQLGcd5ELbI3n2AfX8grFOcF4QuYBxHRK+bESdzSkKy40cBzdI3T5jaBvRQz5O SAdrvcw/XR/B40hXc8kzrLuFDPezpAa6ReGwB2ioa0IPJsxXVWpRS/QjmKwo+Xs= =3Q27 -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] NSA IDA Cryptological Research Centers
JY == John Young j...@pipeline.com writes:
LJ La Jolla Covering Repository
LJ A (v,k,t)-covering design is a collection of k-element subsets, called
LJ blocks, of {1,2,...,v}, such that any t-element subset is contained in
LJ at least one block.
JY What is covering and how does it related to cryptology?
That quote pretty much answers the question. Perhaps an example would help:
Let's choose v=52, like a deck of playing cards (we'll leave the Jokers
inside the beltway). Let's use 23-card blocks (k=23) and 5-card hands (t=5).
The goal to to find a set of 23-card blocks such that every possible
5-card hand can be found in at least one block. Hense, the set of 23-
card blocks covers the set of possible 5-card hands.
That can be done trivially by making the blocks be every possible
23-card hand. But ( 52 \choose 23 ) is about 352 trillion. So we
want to find a smaller set of blocks which cover every possible 5-
card hand.
Their site has one covering for (53,23,5) with 243 blocks. It also
shows that they started with a 272-block covering and worked their
way down to 243 blocks via dynamic programming.
THe application the cryptography is probably something to do with
statistical cryptanalysis. Rainbow tables, maybe?
-JimC
--
James Cloos cl...@jhcloos.com OpenPGP: 1024D/ED7DAEA6
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Asynchronous forward secrecy encryption
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 28/09/13 12:36, ianG wrote: On Thu, Sep 19, 2013 at 09:20:04PM +0100, Michael Rogers wrote: The key reuse issue isn't related to the choice between time-based and message-based updates. It's caused by keys and IVs in the current design being derived deterministically from the shared secret and the sequence number. If an endpoint crashes and restarts, it may reuse a key and IV with new plaintext. Not good. Either the whole session has to be renegotiated then, or you need a way to inject fresh randomness post-crash. It's not good to rely on counters or RNGs in those circumstances. Time ? I'm assuming that if a crash occurs, we can get fresh randomness (e.g. from the OS) after restarting. Is that not a safe assumption? I'd prefer not to rely on time, as the rotation periods for high-latency transports are necessarily long (we don't want to rotate keys while a message is in transit), so after crashing and restarting we may have to wait a long time until the next rotation period starts. I'm assuming the IV is shared in the enciphered message, as otherwise it is unknowable to the recipient if it has 1. in it. Yes - the format is (random IV || ciphertext || MAC), where the MAC is calculated over the IV and ciphertext. (If using an authenticated encryption mode instead of a separate MAC, the IV is included in the additional authenticated data.) It seems we're getting closer to MAC-then-Encrypt. That is, take a HMAC of the plaintext (uses 1, 2). Use that as (part of?) the IV. Encrypt. Deliver the IV + ciphertext. To be honest I don't see a reason to use any function of the plaintext as an IV - I'd prefer the IV to simply be a fresh random value, unrelated to the plaintext, unless there's a reason to doubt that we can generate such a value. I guess I would go back to first principles and ask why we're doing this. Yes, great idea. Here are the requirements as I see them: 1. Protocol obfuscation: Nobody except the intended recipient should be able to distinguish any part of an encrypted message from random bits 2. Unlinkability: Nobody except the intended recipient should be able to tell whether two encrypted messages have the same sender or recipient (except by observing who sends and receives them, of course) 3. Asynchrony: Messages should be deliverable via high-latency transports such as migrating geese 4. Forward secrecy: Encrypted messages should eventually become undecipherable by their senders and recipients 5. Error tolerance: None of the above properties should be lost if messages are lost or reordered in transit And of course the standard requirements of confidentiality, integrity and authenticity. Cheers, Michael -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJSSFO4AAoJEBEET9GfxSfMWOwIAMUXpoCPePO8pwrt4OhEsruS WNXw3DZGzTfEf+Rfe7tYulpxwEgz4BHUUjhTHiNe7jEwyYzq47vA5cglgJQAnvMf fOyeIk4FWhnpgC9MJcBeasBwr9lCxHBm/w2jBfYI5/z9F9fZa8CW7MDhVSrJMdrK rdVwb5hbyfr9UNPrzGfZ0zw6I9uk7e+1x+L7q+ia4ADGIZ3AuJK9JoYz/FGCQbbB 5HWAGoMvGMKqVMvSItN1Aj25oEyOkaPTb6B5ldrFqa97xsQClh1gQZyHJVcC+FTD EvyN06Fl1f9KKjLoDr21hSalqsrV9H3F3iim6y/eXYLbr6PCLNupnmWGdnUWvJw= =3kLK -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] A question about public keys
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Sorry for making so much noise on the list today. I have a quick question about public keys. The Curve25519 paper says that every 32-byte string is accepted as a Curve25519 public key. Yet Elligator doesn't use Curve25519. So I guess there must be a way to distinguish a bunch of Curve25519 public keys from a bunch of random 32-byte strings. What is it? Cheers, Michael -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJSSFT6AAoJEBEET9GfxSfMHLIH/1W98ezG12sqVPAmjcRBauoP EbChv+BzACaOz62I0Jxhc8quGHK3eqYOB0pDtFp2nGWuJpAw7OEKSAVNCABcTO/n OKTk0v24pNCf82RKF2UfAVr43s+cC2N8ApwYobC12Dp1C8DqxiBX+ERS/XleM12b LrPcVW0W6WYcnsK2CgOlENg70XaLDn1bn1M/O+DAsb8ue8nBoXN5UXGMaLRGEkuc jAOBljsiLdPc+gS6waseBuYTWnLk2plnHfrSXOR/1P+rM9rcQgZJsYsPJALzXXeH +ZbSW0+T0NbUMN8kmEhuNOSqGH5CBBpPYzm3dJEXVT1zdBGIyLPQUf475IFZHso= =H7Qj -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] A question about public keys
I should add that the ability to distinguish public DH keys from random is a big deal in some cases. For example, for EKE: there's a passive off-line dictionary attack that can reject a large fraction of possible passwords with each EKE iteration -- if that fraction is 1/2 then after about 20 rounds of EKE you'll have a very high likelihood of having recovered the user's password. This example is hinted at in the Elligator paper (the paper's focus being on privacy protocols). With Elligator (and randomly setting the one bit that is always zero in curve25519 public keys), the passive attacker would have to observe a very large number of EKE rounds before having enough evidence to reject enough possible passwords (that yield public keys larger than 2^256 - 19) to have a good chance of recovering the actual password. Elligator will be a great advance indeed, when it is available. Nico -- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] NSA IDA Cryptological Research Centers
On Sun, Sep 29, 2013 at 09:43:54AM -0400, John Young wrote:
http://www.ccrwest.org/
The latter's web site lists only this offering:
La Jolla Covering Repository
A (v,k,t)-covering design is a collection of k-element subsets,
called blocks, of {1,2,...,v}, such that any t-element subset is
contained in at least one block. This site contains a collection of
good (v,k,t)-coverings. Each of these coverings gives an upper bound
for the corresponding C(v,k,t), the smallest possible number of
blocks in such a covering design.
[snip]
What is covering and how does it related to cryptology?
As is common in math, they define what they mean in the first paragraph.
To paraphrase, they're considering ways to arrange a large number of
sets of things so that a minimum number of blocks is used to enclose
all of the sets.
I'm not a mathematician but that looks like set theory to me. It's the
kind of fundamental mathematical research that frequently arises when
considering some more applied problem space. Such fundamental
approaches frequently have applications in wide-ranging fields; to
compare to a more well-documented example, the 4-color problem first
solved in the 70s generated techniques which ended up being critical to
optimizing C compiler designs for RISC processors in the 90s.
http://en.wikipedia.org/wiki/Four_color_theorem
http://en.wikipedia.org/wiki/Register_allocation#Isomorphism_to_graph_colorability
I doubt that much can be concluded about the activities at the research
site based on their publishing one database in such a rarefied field.
-andy
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] Why non random EC curves are unacceptable.
Although a typical EC curve is unbreakable except by a brute force algorithm of order 2^(n/2), a wide variety of special EC curves have been discovered that allow faster, much faster, methods of breaking. Some of these are so common that any freshly generated curve needs to be checked against them to make sure it is a strong curve. Suppose that the NSA knows some of these that are not known outside the NSA. Then it could generate a trillion curves, until it hits one that is a curve that the NSA can recognize as weak, but that other people cannot recognize as weak. It then makes that curve a standard, and uses the usual state pressures to get it included in all widely used software. Therefore, use Curve25519. Don't use NIST curves. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] A question about public keys
On Sun, Sep 29, 2013 at 9:27 AM, Michael Rogers mich...@briarproject.org wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Sorry for making so much noise on the list today. I have a quick question about public keys. The Curve25519 paper says that every 32-byte string is accepted as a Curve25519 public key. Yet Elligator doesn't use Curve25519. So I guess there must be a way to distinguish a bunch of Curve25519 public keys from a bunch of random 32-byte strings. What is it? Elligator 2 works for Curve25519, see Section 4 of the Elligator paper: http://eprint.iacr.org/2013/325.pdf To your question: Interpreting the 32-byte value as x, check that x^3 + 486662x^2 + x mod 2^255-19 has a square root. This is similar to the distinguisher in Section 1.1, bullet 3 of the paper. Trevor ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] A question about public keys
On Sun, Sep 29, 2013 at 9:29 PM, Trevor Perrin tr...@trevp.net wrote: On Sun, Sep 29, 2013 at 9:27 AM, Michael Rogers mich...@briarproject.org wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Sorry for making so much noise on the list today. I have a quick question about public keys. The Curve25519 paper says that every 32-byte string is accepted as a Curve25519 public key. Yet Elligator doesn't use Curve25519. So I guess there must be a way to distinguish a bunch of Curve25519 public keys from a bunch of random 32-byte strings. What is it? Elligator 2 works for Curve25519, see Section 4 of the Elligator paper: Argh, I meant Section 5. http://eprint.iacr.org/2013/325.pdf To your question: Interpreting the 32-byte value as x, check that x^3 + 486662x^2 + x mod 2^255-19 has a square root. Phrasing this better: check that x^3 + 486662x^2 + x is a square modulo 2^255-19 Trevor ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
