16,773 reputation
12266
bio website
location Paris, France
age
visits member for 2 years, 8 months
seen 29 mins ago

I'm an engineer with experience in applied cryptography, in particular in Smart Card systems.


Mar
17
comment Hash Based Encryption (fast & simple), how well would this compare to AES?
AES-CTR has all the stated properties, and is faster. Security does follow from the assumption that H is indistinguishable from a random function, K is wide enough, and a few other things. However this is not secure with the assumption on H that it is collision-resistant and (first and second) preimage-resistant, thus stating "H is a hashing function" is not enough.
Mar
17
comment Hash Based Encryption (fast & simple), how well would this compare to AES?
AES-CTR has all the stated properties, and is faster. Security does follow from the assumption that H is indistinguishable from a random function, K is wide enough, and a few other things. However this is not secure with the assumption on H that it is collision-resistant and (first and second) preimage-resistant, thus stating "H is a hashing function" is not enough.
Mar
17
comment Randomness test question from FIPS 140-1 and comparison with 140-2
Theses particular tests are no longer mandated, other tests are allowed. Allowing different tests/limits is a practical necessity for some devices, to allow for less false positives. The Change Notices starting page 54 of FIPS 140-2 are relevant. Note: the numbers you list for the run tests are those before change 1. I think I remember reading or hearing (-2 for the precision of that reference) that at least some of the changes from FIPS 140-1 to FIPS 140-2 CN1 are related to the realization that the tests are not independent.
Mar
15
comment RSA problem if i choose two specific small prime numbers?
Your only problem is that what you call message (65) is bigger than n (55). Your result (10) is the message reduced modulo n.
Mar
14
comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
@figlesquidge: DW transformed the question into what formerly was the extension that I suggested. It is easy to turn the answer to that new question into the answer to the original question [with $f:\{0,1\}^n×\{0,1\}^n→\{0,1\}^n$ ], as the condition at most $2^{n-1}$ queries is met by any polynomial adversary in the original question.
Mar
14
comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
@Maeher: chat does not render formula (I tried), so either we end this interesting discussion inconclusively, or we do it here. Do you agree: 1) that$$0\equiv\sum_{x=0}^7R(x)\pmod{2^n}$$has odds $1$ for $R=F''$ and odds $2^{-n}$ for $R$ a random function? 2) mechanically applying the method in the answer to this distinguisher turns this to:$$0\equiv\sum_{x=0}^7R(x)-R(x+7\bmod8)\pmod{2^n}$$has odds $1$ for $R=f$ and odds $2^{-n}$ for $R$ a random function? 3) but actual odds for the above are 1 for $R$ a random function? 4) the method in the answer is wrong?
Mar
14
comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
@Maeher: Let's assume the missing argument is added. As you point, the problem occurs in the random case. The distinguisher I give for $F''$ works (it bets non-random with low odds $2^{-n}$), but the corresponding distinguisher for $f$ built according to the proof's construction does not work (it always bet non-random). Thus, the proof's argument leads to an incorrect conclusion (that $F''$ is a PRF when $f$ is), and is not a correct proof (that $F$ is a PRF when $f$ is; which is true only if, strictly less than $2^n$ queries are made to $F$, when that's not a requirement for $f$).
Mar
14
comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
@Maeher: The proof must contain something to discriminate between $F$ (which is a PRF) and $F''$ (which is not). It currently does not contain this, and I prove it ad absurdum by applying the reasoning in the proof to a working distinguisher for $F''$ $$0\equiv\sum_{x=0}^7 F''(k,x)\pmod{2^n}$$yielding an alleged distinguisher for $f$ $$0\equiv\sum_{x=0}^7 f\big(k,x)-f(k,x+7\bmod8\big)\pmod{2^n}$$The reasoning in the proof concludes this new distinguisher would work, but in fact it does not. I fail to see any simple fix of the proof, or how your comment hints at one.
Mar
14
comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
@Maeher: My point with $F'$ is that " the output looks random " is not justified, and no rationale is given why it is true for $R(x)-R(x−1)\bmod2^n$ but not $R(x)\cdot R(x−1)\bmod2^n$ when $R$ is random. That can be fixed relatively easily. But the proof needs profound change so that it won't transform the working distinguisher I give for $F''$ into one for $f$, specifically a distinguisher based on$$0\equiv\Big(\sum_{x=0}^7 f\big(k,x)-f(k,(x+7)\bmod8\big)\Big)\pmod{2^n}$$which won't work: this expression is true for any function $f$, random or not.
Mar
13
comment How is a public key actually used to encrypt something?
How do you exponentiate a word document? You don't!
Mar
13
comment How is a public key actually used to encrypt something?
BouncyCastle and others unify all cryptographic methods into a single do-it-all API capable of enciphering arbitrary data with any algorithm, including unsuitable for that purpose. That's over-engineering in my opinion, for it becomes all too easy to misuse the API to do non-standard, unsafe and inefficient things, including just what I criticize in your answer. A different example occurred in a recent question where Java's API allowed use of a private RSA key with encryption padding, which is unsafe.
Mar
13
comment How is a public key actually used to encrypt something?
You are right that if the person asking the question has trouble to make the connection between document and number, it is interesting to explain that this transformation could be done. However that fact is irrelevant to " how the message actually gets encrypted ", which is the question. Sound practice is that no part of the document is ever turned into a huge number. When using hybrid encryption with AES, nothing in the plaintext needs to be considered a number higher than 255.
Mar
13
comment How is a public key actually used to encrypt something?
The last paragraph says of the part that I criticize " it is often impractical ", citing a performance reason; that's very different from saying: doing it is never done in standard applications, including for security reason, which would be more accurate. I criticize: " You break up the document into blocks of a particular byte size. Treat each block as a series of bits. That's a number. Feed the number into the crypto algorithm, get a number back out. That's also a series of bits. Now you have turned a series of plaintext blocks into a series of encrypted blocks. "
Mar
13
comment How is a public key actually used to encrypt something?
This answer is wrong. It suggest to apply the asymmetric algorithm to blocks of plaintext small enough to make the interpretation of that as a number suitable for computation. A) That's practically never done in serious systems. B) That's unsafe unless random padding is added (which goes against this description, because with usual padding schemes, plaintext blocks only become a number after padding); in particular, knowing one plaintext, it becomes trivial to recognize that another plaintext is identical in the first block. C) We have more efficient methods based on hybrid encryption.
Mar
13
comment How is a public key actually used to encrypt something?
What is described in the first paragraph of the answer A) is never done; B) would not work at all with common RSA key size, it would require special ones with at least a 800,001-bit modulus; C) slows decryption (making it about a million times slower than for common RSA key size, assuming 2-primes RSA and classical algorithms); D) would not be secure unless random padding is thrown in (without it, knowing a reference plaintext, it would be possible to guess a plaintext with only a small change).
Mar
13
comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
The proof in this question is incorrect even for the standard definition of security using domain $\{0,1\}^n×\{0,1\}^n→\{0,1\}^n$. We could apply it to either of$$F'\big(k,x\big)=\Big(f\big(k,x\big)⋅f\big(k,(x-1)\bmod2^{n}\big)\Big) \bmod2^n$$ $$F''\big(k,x\big)=\Big(f\big(k,x\big)-f\big(k,(x+7)\bmod8+⌊x/8⌋⋅8\big)\Big) \bmod2^n\text{ for }n\ge3$$and it would lead to the wrong conclusion that $F'$ and $F''$ are PRF if $f$ is. In fact there are distinguishers, based on the facts that the low bit of $F′$ is $0$ with odds $3/4$; and that$$\forall k,2^n\text{ divides }\sum_{x=0}^7 F''(k,x)$$
Mar
12
comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
I really appreciate the effort. As pointed in my new comment about the other proof sketch, the simple argument made there must be incorrect, for it works unchanged with a simple counterexample.
Mar
11
comment Long-term data protection, storage of old encrypted traffic and quantum cryptocalipse
@bbozo: You mean Shor's algorithm. There are asymmetric algorithms that claim being immune to that, like NTRU, but I have no informed opinion about that, thus can't make a bottom line. Rather than the impractical OTP, one can use symmetric crypto with large parameters, that's QC-safe.
Mar
11
comment I need a 64-bit cryptographic hash for 96 bits of data
Do you need that the result be computable without a secret? What property must the result have beyond the stated low odds of collision? How many tuples will there be? Is each G unique? Each I? Is it possible to exhibit some less-than-64-bit sub-field of G || I (or some function of that with a small destination set) that is unique?
Mar
10
comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
re-revised: I'll assign the bounty at the end of the bounty period to the best answer according to the following criteria: 1) Includes a correct proof. 2) Uses a standard, or stated and consistent definition of a Pseudo-Random Function family. 3) Gives proof that $F$ is secure for the maximum number of queries $q$ given a small fixed $n$, for some consistent definition of that [see previous comment for an example of definition]. 4) Elegance. 5) Was first [date is that of the revision with essentially the argument in the final version].