19,756 reputation
12779
bio website
location Paris, France
age
visits member for 3 years
seen 7 hours ago

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


Jul
4
comment Getting 88bytes cipher output from 48bytes input in AES
The paper considers that a block cipher's output is wider than its input, likely because the authors confused with some mode of operation of a block cipher complete with IV and padding; that's both for DES and AES.
Jul
4
comment In symmetric searchable encryption are the algorithms public?
In an academic cryptographic context, any algorithm is assumed public (except in specific domains like code obfuscation); that's the second of Kerckhoffs's principles.
Jul
4
comment Is SipHash cryptographically secure?
Ah, yes, that's an excellent reason.
Jul
4
comment Is SipHash cryptographically secure?
Why say "fast"? It only blurs the (valid) argument IMHO. $\;$ +1 for the remark that SipHash could still be a cryptographically strong MAC.
Jul
3
comment Is SHA256 good enough to shrink a key?
No objection...
Jul
3
comment Determine LFSR phase quickly?
If the primitive $P$ of degree $k$ of the generator is not sparse or otherwise unfit, I trust you that we can massage $S/E\equiv x^N\pmod P$ into $A\equiv B^N\pmod Q$, where $Q$ is any primitive polynomial we see fit, and polynomials $A$ and $B$ somehow follow (I fail to tell exactly how, though). We can then solve $A\equiv x^{N_A}\pmod Q$ and $B\equiv x^{N_B}\pmod Q$, and then have $N\equiv N_A-N_B\pmod{2^k-1}$. So at worse, the cost for arbitrary $P$ is twice the cost for any $Q$ we see fit, plus whatever the cost of changing from $S/E\equiv x^N\pmod P$ to $A\equiv B^N\pmod Q$ is.
Jul
3
comment Determine LFSR phase quickly?
I still wonder what the best (known) algorithm is (it seems possible that an algorithm for characteristic 2 beats a general algorithm for small characteristics); its runtime and memory requirements; and how much its runtime depends on $P$ (is it harder for a random primitive $P$ than e.g. the primitive $P$ with lowest possible $P(2)$?
Jul
3
comment Math to replace s-boxes - Good or bad idea?
I can think of $\;$ Pros: simplicity; speed; no cache-induced timing dependency. $\;$ Cons: the outcome does not have all desirable S-box security properties so more rounds are needed, and its hard to tell if that's like two more or twice more rounds; multiplication is not constant-time on many architectures (e.g. low-end ARM).
Jul
3
comment Does collision resistance imply (or not) second-preimage resistance?
@Dingo13: Hopefully, the updated answer will address your comments, and clarify why the paper and its definitions are consistent with: collision-resistance implies second-premimage-resistance; and only shows that an extender that CONSERVES the collision-resistance level of the original may not CONSERVE the second-premimage-resistance level of the original.
Jul
3
comment Determine LFSR phase quickly?
That discrete log algorithm has a name: baby-step/giant step. Yes you can make the cost of searching in the table constant; that can make the algorithm $\mathcal O(2^{n/2})$, but not better. $\;$ There are much betters algorithms, as in Poncho's answer.
Jul
2
comment Determine LFSR phase quickly?
Update: We can do much better than $\mathcal O(2^n)$, where $n$ is the degree of $P$, but I do not know how much better, or starting with how many steps of the generator it is possible to beat the trivial method, or exactly what method is best.$\;$ I see at least a simple method with cost $\mathcal O(2^{n/2})$ and about $n\cdot2^{n/2}$ bits of memory: starting from the final state, we step $2^{n/2}$ times and store the states. Then starting from the initial state we repeatedly advance by $2^{n/2}$ steps using a precomputed matrix, and search that state in our memory.
Jul
2
comment Determine LFSR phase quickly?
If $P$ is the generating polynomial, $F$ the final state, and $G$ the initial state, you are asking is we can find a $j$ such that $F=G\cdot x^j\mod P$, faster than with effort $\mathcal O(j)$ or $\mathcal O(2^n)$. Looks like a discrete logarithm problem to me, and the answer would thus be yes, we can do better than $\mathcal O(2^n)$.
Jul
1
comment Does collision resistance imply (or not) second-preimage resistance?
@Dingo13: I do not see where the paper you cite considers that "collision-resistance does not imply second-preimage resistance", be it without further qualification; or with its refined notions of $(t,\epsilon)\;\text{Coll}$-resistance and $(t,\epsilon)\;\text{Sec}$-resistance when we keep [update: roughly] the same $(t,\epsilon)$ in the two security notions.
Jun
30
comment Does collision resistance imply (or not) second-preimage resistance?
@Dingo13: in the paper you quote, discussion about collision-resistance implying second-preimage-resistance (in the classical sense of that) seems to be left to the the source of the definitions, that is reference [15], P. Rogaway & T. Shrimpton Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance; see the useful figure 1, and the first of 6 properties in their proposition 6 [Conventional implications].
Jun
30
comment Does collision resistance imply (or not) second-preimage resistance?
@Dingo13: No, in this kind of paper dealing with theoretical aspect of security, definitions of security are explicit, or at least given by an explicit reference. In the quoted paper a great number of subtly different definitions of security are given in 2.2, with two pages and a half devoted to that.
Jun
30
comment Does collision resistance imply (or not) second-preimage resistance?
@CodesInChaos: Following your comment, I've been trying to construct a sponge-based hash with capacity $n$, an argument of collision-resistance with effort about $2^{n/2}$, and an explicit second-preimage attack with effort $2^{n/2}$ (rather than a proof of security to effort $2^{n/2}$); but failed. Am I missing the obvious, or is that worth a separate question?
Jun
30
comment Associative standard cryptographic hash function
Probably the simplest collision-resistant answer to the question as currently worded!
Jun
26
comment Convert m-Sequence into a de Bruijn Sequence
@e-sushi: You are looking for x=x>>1^0x8016&-(x&1); to implement the Galois LFSR $x^{16}+x^{14}+x^{13}+x^{11}+1$. This form allows using any polynomial of degree $\mathtt{n}$, if x is at least $\mathtt{n}$ bits, by changing a single constant. The constant is obtained by removing the term $x^\mathtt{n}$ from the poly, and ORing 1<<(n-1-k) for each $x^\mathtt{k}$ term, including 1<<(n-1) for the $1$ term of the poly. E.g. 0x8016 is 1<<(16-1-14)|1<<(16-1-13)|1<<(16-1-11)|1<<(16-1). By contrast, in the formula of this answer (using the Fibonacci construct), each term adds to the code.
Jun
26
comment Is it possible to get better randomness by using multiple PRNGs?
@Stephen Touset: Yes, and in my comment above I'm also making that assumption of seed independence past the first sentence. The rest is to stress that such assumption is NOT enough to ensure that the XOR of the PRNGs behaves at least as well as the worst of the originals in a particular practical test intended to assert a PRNG's quality.
Jun
26
comment Is it possible to get better randomness by using multiple PRNGs?
@Stephen Touset: that's true in an information-theoretic sense, and only with the critical assumption that the PRNGs are seeded from independent sources. However it is possible to devise (bad) PRNGs that individually have output in any particular run indistinguishable from random, but which XOR has horrible properties, even when both are seeded with true random. A trivial example is two identical CSPRNGs modified to entirely ignore their seed input; but it is possible to extend this to make the generators pass many, perhaps any fixed test.