ab praeceptis • October 8, 2016 3:52 AM

Jacob

Indeed, and not at all funny, many if not most (large) primes used in crypto are “pnly quite probably” primes. The problem being that, to be certain, one needs to basically do what the opponent is to do, namely to extensively und fully check for primeness.

On the other hand that’s less of a problem than it might seem and for most purposes a “very likely prime” is good enough, because to make use of eventuall not really primeness requires the opponent to fully and extensively check somewhat less than 1/2 of the space for any given prime(?) number – which again would mean that our prime(?) already served its purpose.

But still, as i.e. Bernstein/Lange demonstrated, a good level of primeness testing is required and unfortunately often not done. There are quite a few out there who limit themselves to rather superficial checking.

It is therefore reasonable to assume that most of the “cyber protection agencies”, some of which (e.g. germany) even openly state that they also want to crack and eavesdrop, will build or have systems with both, large lookup tables and very elaborate primeness checking. I guess that their success rate will be quite shocking.
(Note for lookup tables: This is indeed feasible because there are certain ranges within which the vast majority of primes(?) used in crypto are).

What shocked me personally most is that the (at least open source) crypto community doesn’t seem to care too much about a widely implemented good level of primeness testing.

ab praeceptis • October 9, 2016 12:36 PM

Nick P

“open source” – sorry, but bluntly “No”.

For one because: what is FOSS? It’s everything from excellent professionals to drugged 14 year old losers in romania piling one crap layer on top of another crap layer.

But also “No”, because closed source != not verifiable. Maybe in the usa that doesn’t mean a lot (don’t know, just wildly guessing) but in many other countries (e.g. pretty much all of europe) companies are liable and bound to what they promise. If as, say a french company I assert that my software is fully verified than it’d better be, because if not I’m in serious trouble.

Moreover, there are grey zones. A company can, for instance, have its software (incl. source) externally checked and confirmed. Or it can offer its source under nda for purpose of checking, etc. Have seen that, have done that, not too unusual.

Back to open source and somewhat related: In pretty every OS software they tell you in big fat letters “No responsability, no liability, no nothing whatsowever. Fuck yourself!” That is, in fact, a lot less then what I get from evil closed software (well, some anyway). Also, while an OS project can – and often will – not care a rats ass about its reputation, at least most companies can tolerate only so much bad reputation. (well noted, this doesn’t mean that I’m against OS software. I’m just against evangelizing and preaching the “holiness” automagic wonderfulness of OS).

That aside, the points that drives me really mad and angry is this: We do have researchers, we do have thousands of talented people in universities and hundreds of projects and (at least in most countries) these are payed by tax money – and should hence by default and law make all of their work open source! But alas, they don’t. They rather open a company to monetize what they did being payed for by the public. Yuck!
And yuck again because much of that stuff is of at least modest and sometimes even good quality.

As for verified compilers: Yes, *ML is one good approach, far better than lisp anyway.

I’m currently looking at a “closed loop” system, where each stage of a compiler is double checked, once by itself and once through z3 and where each stage also generates tests for itself. The dirty part obviously being the backend.
An interesting and promising approach, btw, to not only focus on AST or code generation but also on (incl. self-) verification.

In the end there is only one way: proper formal spec … through the diverse stages … to formally verified code generation. With each stage also creating information for verification one can get pretty close to trustworthiness.
Funny sideremark: I’m just rediscovering a Prolog based CLP system as a very useful tool to create lots of helping information such a range checks etc. Funny also because I played a lot with it and learned to value it highly, yet was dumb enough to not notice for a long time what it could do in my main area of interest.

Another issue I meet again and again is that we must stop clumsy annotation games (à la acsl et al.) and have formal specs. in the language itself. Writing functions without at the very minimum Hoare triples or fumbling with vaguely “specified” vars (like “int”) rather than properly spec’d vars (like “x : int 1 … 366”) is just asking for bugs (and making the life of well meaning compiler hard).

One thing that really begs for that (ans being often beasty for formal verif) is loops. I think we should very seriously change our habits and languages; we should, for instance, specify loop not with a processor in mind but with an algorithm in mind. Specifying a loop invariant should obviously be a standard part and not an exception for paranoid developers writing a comment annotation.

ab praeceptis • October 9, 2016 5:17 PM

Gerard van Vooren

a) that already has been done, albeit with some ugly sidenotes (VCC) or too little (e.g. Ivy)

b) the way it has been done isn’t that far away from something like, say, “Secure C”. C parsers are beasts but it’s not like it couldn’t be done.

c) While I agree that C has probably the most urgent need, there are are more or less widespread and sufficiently powerful languages that could profit from such an undertaking.

[d) btw, I guess you mean Spark, not Ada; but no problem, I got understood you].

ab praeceptis • October 10, 2016 7:49 AM

Thoth

Just a quick in between wondering/question: Can your java-whatever make use of the chips security accel? While this is typically rather primitive in smartcard chips, there usually is at least some accel blocks like montgomery, etc.

I’m asking because the numbers you published seem to strongly suggest that you do not make use of those facilities (and because I’m dumb re. java).

ab praeceptis • October 10, 2016 9:42 AM

Thoth

I might be badly mistaken, but: You talked about 345 KB in ca. 2 Minutes which is a little less than 2,9 KB/s. On the other hand you say (and I don’t doubt it) that your Infineon chip is capable of doing 256 Bytes in 4 ms, i.e. 345 KB in ca. 5.5 s.

Yet you need ca. 120 s.

I see two major candidates to completely f*ck up your times: a) the java in “javacard” (incl. your assumptions on the OS) and b) PBKDF2.

As you seem to stick to the “standard” (rather arbitrary and doubtful stuff based on rsa’s musings) you have >= 1.000 iterations of sha-1 with some mumbo jumbo around. It goes without saying that a KDF is expensive; after all that’s it’s raison d’etre.

To get something like a vague grip on your situation I based myself on the assumption that your implementation on supposedly making good use of HW crypto accel. javacard is wrong and to encrypt 256 Bytes actually takes 10 * 4 ms = 40 ms. This brings us into the ballpark of 55 s for sym. encryption alone and leaves another minute for KDF (which seems plausible) during which the setup/PBKDF2/SHA-1/rsa mumbo jumbo runs.

Again, I’m quite clueless and dumb re. java whatever, but I know a thing or two about crypto (incl. implementation). From what I see, that whole thing is ridiculous. Not your efforts! Nor the chip but the javacard blah thingy. I have reason to trust that you know your stuff and I happen to know that Infineon are quite smart in the smartcard chip field. So, from my POV java* is the culprit and slows you down by a factor of almost 20. This roughly matches what I would expect from a non accelerated pure software implementation on that class of chip.

I can’t help you a lot due to my java ignorance but from what I see, you should have a close and tough look at your premises, in particular the javacard OS.

ab praeceptis • October 10, 2016 10:19 AM

Thoth

Oh no. Those lousy results just with aes-256 alone? Unless you or Infineon are grossly lying – neither of which I assume – it seems blindingly obvious to me that your sw doesn’t use any hw accel. at all.
120s vs 5.5s for aes-256 hardly leaves any other explanations.

I just hope that you find a way to make the underpinning java-crap use the chips hw accel.

Good luck! (friendly and honest)

ab praeceptis • October 10, 2016 10:41 AM

Thoth

P.S. I’d like to suggest that you build and run a quick and dirty test in which you simply run sha-1 over 1.000 iterations (feeding it’s output into its next cycle input and starting with whatever arbitrary string) to get a rough ball park figure of what to expect from PBKDF2. To extend that guesstimate you might want to switch sha-1 and sha-2 and run 1.000 cycles again.

Such you would at least have a rough idea of what we’re talking about in terms of runtime and where some optimization is needed most.

BTW: aes-256 is a ridiculously fast algo (not the fastest but very fast anyway). Looking at a typical SLE78 spec, the timing numbers you tell would suggest that the chip needs over 11.000 cycles per Byte on aes-256. This is way out of any reasonable expectation for a cipher like aes-256. Well noted, this is even way out for a clumsy software only implementation.

ab praeceptis • October 12, 2016 6:13 AM

CallMeLateForSupper, Thoth

I’ve seen some “quasi-OTP” is use. It came basically down to: Use a really good PRNG with a very high cycle etc. Then exchange but 2 seeds, one of which is the start seed and the other one is used to seed a channel selector (a way of reseeding).

From then on the parties exchange but short numbers which tell the other side how many cycles to go through on PRNG 2 to define the channel on PRNG 1 which then produces the key for sym en/decrypt the message.

Disadvantage: No reservoir of OTP keys
Advantage: No reservoir of OTP keys

In other words, you basically exclude the danger of having your OTP being exhausted and/or found but on the other hand it’s just a quasi OTP.

Some dislike that, saying that it’s not the real thing. I, however, do like it a lot, mainly for three reasons:
a) after all, an OTP is but the output of high quality random.
b) it solves another problem, too, namely the whole (non pq) PK issue. Assuming one has physical contact from time to time, which is a very reasonable assumption for companies, banks, etc, the parties have a “new” and random key for each and every contact/transmission/session with the need to rely on PKE (SSL/TLS …).
c) It can be arranged such that neither party has the “OTP” which is attractive because an OTP list/CD-Rom/* can become a liability very quickly. Moreover OTP means one has to put trust in those holding the list.

In fact, I happen to know at least one company who have something like this in place for day x, when PK gets brutally weakened in a post quantum scenario (which, of course, isn’t perfect in that it relies on the fact of Shores algo successfully running on an actually useable Q-system is not necessesarily published right away. While a corp. player is very likely to brag immediately to conquer the market state players might prefer to stay in the shadow)

ab praeceptis • October 12, 2016 8:08 AM

Oh hell, what did I start there *g

TRNG or PRNG is a non-issue in my eyes, provided one has a PRNG of high enough quality. In the end it’s simple: An OTP is RNG-based, too; so it comes down to a classical choice of priorities and both have their disadvantages and advantages. A true OTP mechanism is not deterministic and hence both sides must have the current material. This, however, opens a problem class. A deterministic Prng-based mechanism avoids most of those problem but opens some problems, too, most of which dome down to PRNG quality.

Clive Robinson is, of course, right, when he points out Trng vs Prng, the latter supposedly being usually worse over some parameters. BUT: random distribution and some other factors are not the decisive point here because we do not use the RNG output for encryption but we use it as key for sym. crypto. So the relevant factors like random distribution, etc. are anyway defined by the sym. crpto.

Let’s look at it properly. Say our PRNG is 64-bit. As P1 drives P2 this already opens a hefty set of variations. Now feed that into a good, say, 256 bit hash whoose output you then use as key for, say, salsa 20 (btw. Thoth, I agree. The mere fact of aes being nist makes me consider it as tainted).

Good luck attacking that. Also good luck proving that the net security of that is relevantly worse than OTP.

Bonus: That mechanism is multifactor, non PK and pq-secure.

Would I use that for the highest level state secrets? Maybe but probably not (I’ve learned to be conservative). Would I use it for some company? Every day of the week and smilingly.

ab praeceptis • October 12, 2016 9:49 AM

r

Somewhat simplifying one can say that both sym. crypto and PRNGS are no significant speed problem, even on embedded CPUs (for which one might anyway prefer small HW optimized algos such as e.g. rabbit).

The performance problem is with PK and with KDFs and similar. bcrypt, which you mention, is an example. Those are expressely designed to be expensive and such to make the lives of crackers harder.

Side note: The thing those algos strive to defend against is when some opponent already has, say, your pw database; they strive to immensely drive up the necessary efforts, for instance by needing to run thousands of hashing rounds which also makes precomputed rainbow tables all but meaningless.

Side note 2: The quality (sometimes according the target) is quite different. The better KDFs address multiple factors, such as computing power as well as memory, which, if well designed, can limit the usefulness of massive parallel approaches.

Side note 3 (not making friends, I guess): Regarding PKE your “simplicity” argument is quite relevant. One of the problems of not-simple being that also modelling, verification, and math proving get exponentially more complex.

That’s quite valuable in simple designs: You can consider the algos (e.g. PRNG 1 and 2, Sha-256, salsa-20) as elements of a serial mechanism which also allows you to apply rather simple and strong logic to each element.
I find it an interesting property that one can simplify it to the point of saying that there are only 2 approaches for the opponent. He can either attack the encrypted message, in which case he has to break a strong (but cheap) sym. algo, say, aes-256, or he can try it from the front. And thats where the mechanism I talked about shines again. Being multifactor and (high quality PRNG based) he will be out of luck even if he, which is a classical nightmare assumption, were in full control of the network and managed to copy the couriers envelope.

I think that is actually the most promising approach: to rely on simple, well proven “building blocks”. And it’s the problem of PK, which, one must say for the sake of fairness, addresses a vastly more difficult problem class and has to do with a rather limited set of well understood one way functions.

(In case your post was just meant as a joke: OK, you got me. I’m an idiot *g)

ab praeceptis • October 12, 2016 12:22 PM

Markus Ottela

I get your point and you are right, if one looks from a stringent and theoretical perspective.

However, the mechanism I talked about (and called quasi-OTP) doesn’t strive to replace OTP or to be an alternative real OTP (let alone in the strict sense). Rather it strives to get rid of PKEX and it does so by using some principles of OTP.

“64-bit PRNG not good enough” – oh well, then we should forget about quite some nice HWRNGs that happen to deliver single bits. More seriously, we can apply the same mechanism, i.e. we can grab more than 1 chunk of output; where some HWRNGs grab 256 1-bit outputs we can grab 4 64-bit outputs. In the given case it was decided to use a 256-bit hash as a spreader. Yes, you are right, that means that we still use only 2^64 of the available 2^256 states/outputs. So what? If that was a problem then we should stop using 256 (or more) bit hashes right away because chances are that we’ll not use their full space anytime soon. Obviously however that’s not a problem.

Finally and most importantly, I’m talking about keys, not about encryption, which is done using some well established sym. crypto algo.

As for alternatives (again, note that the mechanism I talked about is targetting to keep PKEX out, not to replace OTP) I’d like to share an interesting point: I know of 1 (in words “one”) algorithm that generates provable primes. iirc openssl is not even applying reasonably state of the art primeness probability(!) tests, nor does gmp. In other words: Very many PKEX out there are running with lousily checked prime probability and they are, well noted using algos that very much rely on primes being prime.

I get your points but the context must be considered. We are rarely in the situation to freely chose from diverse perfect alternatives; this is particularly true in key exchange.
You may judge differently and I respect that but for me a proven 64-bit random key space, that for most opponents is de facto a 256 bit key space, is much more useful than a bazillion bit keyspace relying on lousily checked probable primes and implemented in questionable (and actually proven lousy) code (not to talk about the protocol).

As for your 3 courier envelopes stolen/copied: So what? One can comfortably and easily prepare solutuons for that case and one could also easily and simply introduce backup and/or alternative channels. That doesn’t worry me (nor said company). And btw, when you introduce weaknesses with the courier (which, well noted, can exist) you should also introduce an Eve that steals/copies OTP material (and such breaks/poisons your complete scheme).

Last but not least: All I did was to talk about a mechanism I found interesting. You don’t like it? No problem; I don’t want to convince or to evangelize you. You feel, only real OTP based on real (HWRNG generated streams) should be used? Fine, no problem. Actually I know cases where I would prefer/choose that myself. But I also know cases where I wouldn’t and where T’d consider a weaker (mathematically) solution to be actually stronger in practical terms.