My question is about Enigma rotors I found this explanation of Enigma rotor movement on this website, but can't quite understand the methodology: Enigma rotation example

A ⤑ B → D ⤑ C (rotor III in position B)
C ⤑ C → D ⤑ D (rotor II in position A)
D ⤑ D → F ⤑ F (rotor I in position A)
F ↔ S (reflector B)
S ⤑ S → S ⤑ S (rotor I in position A, reverse)
S ⤑ S → E ⤑ E (rotor II in position A, reverse)
E ⤑ F → C ⤑ B (rotor III in position B, reverse)

I follow steps 2 to 6 inclusive OK, but unsure about steps 1 & 7:
I understand that the rotor moves before encryption, so I get the A>B>D, but why the final D>C? and similarly the end of step 7.  I can't understand where that final step comes from.
I guess there is a similar bit of complexity when the the rotors cause the next one to step ahead when the notches engage?
I'm only doing this for interest, as I used to use AES a lot in my job (now retired), encrypting electronic messages, so thought I'd get my head round Enigma to keep the brain ticking over.
Think I understand now (correct me if I'm wrong)!:
Because the rotor has advanced, pressing A goes into rotor III at letter B, which encodes to D, but "comes out" in "position" C because the rotor has advanced.

I created a spreadsheet "picture" which explained to me how the encoding & wiring works to encrypt the letter 'A' twice, starting with all 3 rotors in the 'A' position.


Composing hashes and/or MACs Suppose I have n hash/MAC functions, of which n-1 are extremely insecure, leaving only one that is in fact cryptographically secure. If I use all of them on a message and the XOR them together the result will be cryptographically secure or not?
I believe it would, because if 1 is secure than it's output is undistinguishable from random, and will act as a one time pad for the insecure ones. Is this reasoning sound?

It is safe, in the case that you have MACs which are independently keyed (or at the very least, the cryptographically secure MAC is independently keyed from all the other ones).  This can be seen not by an argument from randomness, but from a simple observation that it were not true, then an attacker could attack the secure MAC by generating the insecure MACs on his own, exclusive-or those MACs into the MAC he did observe, and then attack the combined MAC; any weakness there could be translated into a weakness in the original secure MAC.

If you have MACs which are not independently keyed, or you have hashes, you can construct cases where the XOR is not secure.  Here is one such example:

Our secure hash is SHA256 (which for the purposes of this example we will assume is secure).
We have 256 insecure hashes, $X_0$ through $X_{255}$.  $X_i$ is defined this way; all bits of $X_i(M)$ are 0, except for bit $i$; bit $i$ will be the same as bit $i$ of $SHA256(M)$.

We can see that every $X_i$ is extremely insecure (as each "hash" has only two possible values).

And, we can trivially see that the exclusive or $SHA256(M) \oplus X_0(M) \oplus X_1(M) \oplus ... \oplus X_{255}(M)$ is also insecure (because it is always zero).


Security of AES CTR with multiple messages containing the same known plain text I have this scenario:

The same plain text (that is part of an unkown bigger message) is being ecrypted multiple times using AES 128 CTR with a random key, the key is being transfered encrypted using RSA public key.
For example:

(www.myBlog.com, some_random_text)

The location and the content of the plain text doesnt change.

Is there a way to break the AES? ( Assuming I know the plaintext)

I have full man in the middle.

This is a type of chosen-plaintext attack, where the adversary gets partial choice of plaintexts — they can cause the same substring to be encrypted multiple times.

AES-CTR, if used properly, is resistant to chosen-plaintext attacks.

Used properly, for CTR mode, means that the same counter value must not be reused for different messages. For example, if one message is 48 bytes (3 blocks) long and is encrypted with the starting counter value 12, this uses up counter values {12, 13, 14}. Other messages must never use those counter values; for example, another 3-block message may use {9, 10, 11}, but not {14, 15, 16}.

CTR encryption calculates $N_i \oplus P_i$ where $N_i$ is the counter value for the $i$th block of the message and $P_i$ is the plaintext. If a counter value is repeated ($N_i = N_j$ with $i \ne j$, whether within the same message or in different messages encrypted with the same key), the xor of the two ciphertexts is $(N_i \oplus P_i) \oplus (N_j \oplus P_j) = P_i \oplus P_j$; if the plaintext for one of the blocks is known or guessed then so is the plaintext for the other block.


Rule 30 Cellular Automaton for Cryptography Steven Wolfram of Mathematica uses a pseudorandom number generator based on Rule 30 for applications in Mathematica software but I would like to know if a pseudorandom generator based on Rule 30 is cryptographically secure? Can anyone weigh in on this?

… I would like to know if a pseudorandom generator based on Rule 30 is cryptographically secure?

No. Cellular automata rules are not cryptographically secure; not even close.

Rule30 works somewhat like an LFSR… it's a cellular automata rule (think: finite state machine) having alike problems with repeating patterns (even though with different, expanding repetition — in contrast to how LFSR work), typical finite state machine behaviour, and rather short loops of repetition.

Visualizing Rule30 and the likes can show this in an more "in your face" way — where it becomes rather obvious why you wouldn't want to use "cellular automata" for things like cryptography.

Meanwhile (since the 80s) cryptographic engineering has better building blocks than those "old goodies". For similar reasons, more modern crypto algos stopped using LFSR combining constructions.

Sure… you could use Rule30 in cipher algo design - but the drawbacks and problems of working around cellular automata issues will make the whole algo more suspicable to attacks. This again will make the whole algo less optimal from a resource and certainly from a speed point of view.

Differently stated: just because you could, doesn't mean it makes sense. Especially, since things like Rule30 don't help adding security to your algo as they're not cryptographicall secure by nature… and making cellular automata rules cryptographically secure is comparable with making an LFSR cryptographically secure. It can be done, but the problems will always tend to outweight the gains from choosing such a component for cryptographic engineering purposes.

For example: when we look at the several stream cipher designs based on cellular automata since the 80s, it shows that — most of the time — even a rather simple attack with a SAT solver is already more efficient than a brute force attack. That means most of them are theoretically broken the day they are published (while practical breaks are waiting atround the corner). Especially when looking at cellular automata, such SAT solver attacks are merely the tip of an iceberg which tends to be full of problems includng timing attacks, etc.


Verifying a downloaded file with an .asc file I downloaded CentOS 6.8 for 32-bit over torrent. It comes (among other things) with a sha256sum.txt file and a sha256sum.txt.asc file. I know how to verify the signature of a file when I have the encryption key, but in this case, what would be the encryption key to import?

OK, so Paul already shows the site where they explain what you need to do. I'll explain how this helps you to verify the files you downloaded.

Lets start with the .asc version, which consists of a set of hashes and a GPG (or actually OpenPGP) signature. To verify the signature you need a public key. Now if you've already got a CentOS system you may already have it installed on your machine. If not you can download it (per instructions) and verify it with the fingerprint. The fingerprint is on a HTTPS protected page on the main site, so this way you can trust the public key. Therefore you can also verify the signature with it. To compare the fingerprint this way is slightly tricky as an attacker could have taken over the main site. Then again you only need to do this once and then keep the key on your system (so the window of attack should be minimal).

This is the difference with the sha256sum.txt. If the site or mirror is taken over then an attacker may replace the sha256sum.txt, giving you only a false sense of security. If you download this file then you should download it from the main site, preferably protected by TLS, not from a mirror.

Downloading the .asc is still preferred as it is likely signed when the build is generated, on an back-office computer.

Don't use sha1sum.txt or sha1sum.txt.asc, it's not as secure due to vulnerabilities within SHA-1.


In short: Trace back where bits come from in every byte in the output state (8 bytes) of the SP_network.

In one round, after we have xored the round key bits,
we have 8 bytes (a 64 bit word, with rightmost byte 0, leftmost byte 7 etc.
which in the linked software (which is byte oriented) is represented as state[0] to state[7]) are put nibblewise through the S-box: this is easy to do as a byte substitution as well. Then we trace where the bits in the post-permutation state come from (generated by a simple program, here the part for output byte 0, i.e. state[7]:)

bit 0 = byte 0, subbit 0  from byte 0, subbit 0
bit 1 = byte 0, subbit 1  from byte 0, subbit 4
bit 2 = byte 0, subbit 2  from byte 1, subbit 0
bit 3 = byte 0, subbit 3  from byte 1, subbit 4
bit 4 = byte 0, subbit 4  from byte 2, subbit 0
bit 5 = byte 0, subbit 5  from byte 2, subbit 4
bit 6 = byte 0, subbit 6  from byte 3, subbit 0
bit 7 = byte 0, subbit 7  from byte 3, subbit 4

We see that we use the bits 0 of the two S-box nibbles (which are 0 and 5 in the byte) to build a half-nibble (bits 0,1 or bits 2,3 etc.) of an output byte.  So we can start building four byte-indexed tables, say T0,T1,T2,T3 with the constraints that

T0[b] & 0x03 equals the bits 4,0 from SS[b] (i.e. the double nibble byte S-box.)
T1[b] & 0xc0 equals the bits 4,0 from SS[b]
T2[b] & 0x30 equals the bits 4,0 from SS[b]
T3[b] & 0xc0 equals the bits 4,0 from SS[b]

That way we can build up post-permutation byte 0 or state[7] as a bitwise-or
of masked outputs from these 4 tables (which we want to construct).

To build up the next to last byte 1 (state[6]) we have the following similar pattern:

bit 8 = byte 1, subbit 0  from byte 4, subbit 0
bit 9 = byte 1, subbit 1  from byte 4, subbit 4
bit 10 = byte 1, subbit 2  from byte 5, subbit 0
bit 11 = byte 1, subbit 3  from byte 5, subbit 4
bit 12 = byte 1, subbit 4  from byte 6, subbit 0
bit 13 = byte 1, subbit 5  from byte 6, subbit 4
bit 14 = byte 1, subbit 6  from byte 7, subbit 0
bit 15 = byte 1, subbit 7  from byte 7, subbit 4

So the same tables can be re-used but on different S-box output bytes.

Next we consider byte 2, state[5], again from the same output:

bit 16 = byte 2, subbit 0  from byte 0, subbit 1
bit 17 = byte 2, subbit 1  from byte 0, subbit 5
bit 18 = byte 2, subbit 2  from byte 1, subbit 1
bit 19 = byte 2, subbit 3  from byte 1, subbit 5
bit 20 = byte 2, subbit 4  from byte 2, subbit 1
bit 21 = byte 2, subbit 5  from byte 2, subbit 5
bit 22 = byte 2, subbit 6  from byte 3, subbit 1
bit 23 = byte 2, subbit 7  from byte 3, subbit 5

So to build up that byte we need the half-nibble built from the bits 1 of the S-box output (1,5 of the SS-box byte), so the constraints change slightly, where the order of the tables has been changed to get non-contradicting restraints (the lowest bits of T0[b] have already been fixed, etc.), so I use them cyclically:

T1[b] & 0x03 equals the bits 5,1 from SS[b]
T2[b] & 0x0c equals the bits 5,1 from SS[b]
T3[b] & 0x30 equals the bits 5,1 from SS[b]
T0[b] & 0xc0 equals the bits 5,1 from SS[b]

The same tables and masks can be re-used for byte 3 (state[4]) as witnessed by

bit 24 = byte 3, subbit 0  from byte 4, subbit 1
bit 25 = byte 3, subbit 1  from byte 4, subbit 5
bit 26 = byte 3, subbit 2  from byte 5, subbit 1
bit 27 = byte 3, subbit 3  from byte 5, subbit 5
bit 28 = byte 3, subbit 4  from byte 6, subbit 1
bit 29 = byte 3, subbit 5  from byte 6, subbit 5
bit 30 = byte 3, subbit 6  from byte 7, subbit 1
bit 31 = byte 3, subbit 7  from byte 7, subbit 5

Thirdly, for byte 4 (and again, similarly 5) we see

bit 32 = byte 4, subbit 0  from byte 0, subbit 2
bit 33 = byte 4, subbit 1  from byte 0, subbit 6
bit 34 = byte 4, subbit 2  from byte 1, subbit 2
bit 35 = byte 4, subbit 3  from byte 1, subbit 6
bit 36 = byte 4, subbit 4  from byte 2, subbit 2
bit 37 = byte 4, subbit 5  from byte 2, subbit 6
bit 38 = byte 4, subbit 6  from byte 3, subbit 2
bit 39 = byte 4, subbit 7  from byte 3, subbit 6

where we build succesive half-nibbles all from the different
masks of the combination of bits 6,2 (bit 2 from a single S-box)
of the SS-box output. So again we can build new constraints, going on cyclically from before:

T2[b] & 0x03 equals the bits 6,2 from SS[b]
T3[b] & 0x0c equals the bits 6,2 from SS[b]
T0[b] & 0x30 equals the bits 6,2 from SS[b]
T1[b] & 0xc0 equals the bits 6,2 from SS[b]

where we can re-use the exact same bitwise-or recipe for byte 5.

Finally, for bytes 6 (and 7) we get as the origins:

bit 48 = byte 6, subbit 0  from byte 0, subbit 3
bit 49 = byte 6, subbit 1  from byte 0, subbit 7
bit 50 = byte 6, subbit 2  from byte 1, subbit 3
bit 51 = byte 6, subbit 3  from byte 1, subbit 7
bit 52 = byte 6, subbit 4  from byte 2, subbit 3
bit 53 = byte 6, subbit 5  from byte 2, subbit 7
bit 54 = byte 6, subbit 6  from byte 3, subbit 3
bit 55 = byte 6, subbit 7  from byte 3, subbit 7

So we use the combination of bits 7,3 (or bit 4 from a single S-box)
from different bytes to form this byte. So the next set of new constraints
becomes:

T4[b] & 0x03 equals the bits 7,3 from SS[b]
T0[b] & 0x0c equals the bits 7,3 from SS[b]
T1[b] & 0x30 equals the bits 7,3 from SS[b]
T2[b] & 0xc0 equals the bits 7,3 from SS[b]

Now we can gather the results: to actually find T0[b] we
consider all we know about it from before:

T0[b] & 0x0c equals the bits 7,3 from SS[b]
T0[b] & 0x30 equals the bits 6,2 from SS[b]
T0[b] & 0xc0 equals the bits 5,1 from SS[b]
T0[b] & 0x03 equals the bits 4,0 from SS[b]

and compute the table directly. It will be the table pmt_3 from
your linked software. This code (gist on GitHub) will compute these combined tables (in a slightly different order I believe then used in the linked software) to see how to do this in more detail.


Does this describe an invalid key share attack? I recently came across a mention of invalid key share attacks on this site. It is done with DH groups over $\mathbb{ℤ}_p$ :prime $p$, where $p = qh + 1$, where $q$ is the prime order of DH subgroup used, which can reveal $s$ s.t. $s \equiv x \bmod t$, given public key $X = g^x$, $x$ being a DH private key and $g$ being the generator of the subgroup. Where $t$ is some factor of $h$. I looked for it and could not find anything about it. I thought for a while and I think I know what it is. Can you please correct me if I am wrong?
For a simple example, I consider $p$ to be a safe prime so the subgroup should be the subgroup of quadratic residues modulo $p$. So let's say we have DH oracle with private key $x$ which takes as input a DH public key $Y = g^y$ and outputs $S = Y^x$. An attacker instead of feeding $Y = g^y$ to the oracle instead feeds $Z = g'^z$ where $g'$ is a primitive root modulo $p$ and $z$ is odd. It is an invalid public key because it does not belong to our subgroup. But the oracle ignores it and outputs $S' = Z^x = g'^{xz}$. Using the Legendre symbol, we calculate whether $xz \bmod p-1$ is even or odd which reveals whether $x$ is even or odd since $p-1$ is sure to be even. I am sure it is similar for other values of $h$ as well. Of course, it can be easily thwarted by having the oracle check whether or not the query is indeed a quadratic residue modulo $p$.
why to use a safe-prime in Diffie-Hellman key exchange?
EDIT:
I thought of a new way that does not need oracle access. Since $p ≡ 3$  (mod 4), as $(p-1)/2$ is a prime number, each member of the subgroup must have two square roots, one quadratic residue and one non-residue. By choosing $g'$ as one of the square roots of $g$, whichever is a non residue, the attacker can get a diffie-hellman shared secret by trying  $(\pm \sqrt{X})^z$. If authentication with shared key succeeds with the quadratic residue one, $x$
was even otherwise it was odd. This way we don't need an oracle that just spits out DH shared result.

Can you please correct me if I am wrong?

What you have is essentially correct; however it can be generalized a bit.
In real systems that use DH, the honest system will take the shared secret and do something with it; commonly putting it (and some public information that the attacker knows) through a KDF, and then using the keys generated by that KDF to either encrypt or decrypt a message.  TLS would be an example of this.
What this means is that the attacker can verify a guess to the shared secret (by sending that guess through the KDF, and then seeing if the keys generated will decrypt the message from the honest system, or using the keys to encrypt a message that is sent to the honest system (and seeing if the honest system acted as if he could decrypt the message)
Here is how the attacker can exploit that to find $x \bmod t$ (where $t$ is a small factor of $(p-1)/q$); he finds a value $j$ that is of order $t$, he picks a random $y$ and sends as his key share the value $j \cdot g^y$.  The honest system will compute $(j \cdot g^y)^x = j^{x \bmod t} \cdot g^{xy}$.  The attacker knows the value $g^{xy}$; this gives him a way to test various values of $x \bmod t$.

Of course, it can be easily thwarted by having the oracle check whether or not the query is indeed a quadratic residue modulo $p$.

Or more generally making sure that $y^q = 1$.  However, that is expensive; other possible defenses are:

Simply never reusing a private value; this means that an attacker can learn some information about the value $x$ we used with an exchange with him - however, we wouldn't care if he could retrieve the entire $x$ value, as we allow him to learn the shared secret, and that's the only thing that $x$ would give him.

Use a slightly larger value of $x$; for safe primes, $h=2$, which means that the attacker can learn the lsbit of $x$ and nothing else.  Hence, if we select our $x$ value from a range 1 bit larger than we would have otherwise, then we have kept the discrete log problem just as hard (even if he learns that lsbit)


Edwards / Montgomery ECC with Weierstrass Implementation? So let's assume I want to perform Ed448 or Ed25519 digital signatures or want to perform a DH key-exchange. Assume further that those curves (Curve448 or Curve25519) are required.

But the problem is, that I have only a constrained device given, which only allows for Weierstrass-Computations. Alternatively I have a software library that can perform Weierstrass-Operations but not Montgomery / Edwards operations. "Operations" here denote point addition and scalar multiplication. Note further that both devices / libraries support arbitrary (Weierstrass) curves.

So this provokes the question:
Is it possible to perform Edwards / Montgomery operations using a Weierstrass engine and if so, how?

If I understand your question correctly, you are essentially asking if points in Edwards and Montgomery curves can be represented in Weierstrass coordinates. This is true; in fact, any elliptic curve over a field of characteristic $\neq2,3$ can be represented in Weierstrass form $\mathcal{E}_{w}^{a, b} : y^2 = x^3 + ax + b$, and by extension its points can too.

The question, then, becomes “how easy is the conversion”?

For Montgomery curves of the form $\mathcal{E}_m^{A, B}: By^2 = x^3 + Ax^2 + x$, it is surprisingly straightforward. You can map the point $(x, y) \in \mathcal{E}_m^A$ to the Weierstrass curve $\mathcal{E}_w^{1/B^2-A^2/3B^2,A(2A^2 - 9)/27B^3}$ via the map $((x + A/3)/B, y/B)$. The inverse map is obvious, $(Bx - A/3, By)$. If $B=1$, which is the case for every Montgomery curve used in practice, this simplifies substantially.

For twisted Edwards curves $\mathcal{E}_{e}^{a, d} : ax^2 + y^2 = 1 + dx^2y^2$ (where Edwards curves are the subset where $a = 1$) there also is a simple map to a Weierstrass curve, which consists of converting the curve to Montgomery format first. In particular, we can map $\mathcal{E}_e^{a, d}$ to $\mathcal{E}_m^{2(a + d)/(a - d), 4/(a - d)}$ via $(x, y) \mapsto \left(\frac{1 + y}{1 - y}, \frac{1 + y}{x - xy}\right)$, with inverse $(x, y) \mapsto \left(\frac{x}{y}, \frac{x-1}{x+1}\right)$. Composing theses maps with the above, we get maps to the appropriate Weierstrass curve $\mathcal{E}_w^{a, b}$. None of these conversions are terribly expensive compared to the cost of a scalar multiplication.


Why NaCL does not provide anonymous public key cryptography? At the same time Sodium provides API for anonymous encryption without using ephemeral keys.
Is it a bad practice to just use other user public key to encrypt a message?

As I now understand the question: why doesn't NaCL provide a primitive for unauthenticated encryption, making ciphertext blobs that are only decrypt-able by a receiver identified by their public key?  Note libsodium provides crypto_box_seal which does exactly this and NaCL claims to (try to) provide all necessary crypto primitives.

In answer, notice crypto_box_seal can be built using other primitives.  Sodium says of crypto_box_seal:

ephemeral_pk ‖ box( m, recipient_pk, ephemeral_sk
                  , nonce=blake2b(ephemeral_pk ‖ recipient_pk))

So what we have in terms of NaCL prims are (pseudo-code):

sk = random();
ephemeral_pk = crypto_box_keypair(sk);
nonce = sha512(ephemeral_pk || recipient_pk); // NaCL uses SHA512 not Blake2b.
ct = ephemeral_pk || crypto_box(m, recipient_pk, sk, nonce);

This can be considered anonymous because the ephemeral key pairs used are not associated with any identity - the secret key should be destroyed immediately after computing the ciphertext message, ct.


Is there a way to bruteforce the private key of this cryptocurrency altcoin? In the end of 2013 or the beginning of 2014, I bought 80 000 Applecoins (APC) for 0.1 Bitcoins and got another ten by an airdrop, so I had a total of 80 010.  I never spent the coins, and when a coinswap to a new version of Applecoin (APW) happened, I was too late to take advantage of the exchange offer, as I wasn't monitoring the coin then.

Fast forward to today. I simply could not find any copy of my wallet, and I looked on all my backup drives, simply not there. I don't specifically remember backing up the wallet, but I always do so when I run a wallet for a new cryptocurrency for the first time.

Well, all I have now is my public address and the password for the Applecoin wallet. Now the question is: Is there a chance that I can restore my private keys and basically my wallet by somehow bruteforce it?

In the Ethereum stack somebody posted a script with which he could restore his private keys just with the address and password. Is there a chance for me? Because nowadays only the new Version, APW is listed as active, the old one, in which I have the my balance of those 80 010 coins, is inactive.

First up: APC != APW. The later is a different fork, which you missed to follow… costing you cash. Besides that my research showed that the original APC coin site is down, 99.9% of its block explorers are down, and only the most exotic exchanges list APC (naming it AppleCoin, AppeCoin, AlphaCoin, etc. all using the same APC short notation) which are clear warning signs that the 2013 APC AppleCoin currency is down and out ever since they forked it into APW.

Answering the core of your question

Having said that, cryptographically the wallet recovery based only on public key(s) and wallet password is infeasible as it would mean brute-forcing your public keys to recover private keys. This is much harder (from a time & resources perspective) than mining cryptocurrency, so thinking about brute-forcing is a futile effort.

The password you've got protected the database your wallet used. That's not helpful when trying to recover your private keys… unless you have a backup the wallet database — which you stated not to be available.

My advise: learn from the experience and move on… while constantly reminding yourself that regular backups of important data (all data, not only financial data) can save you from a lot of frustration and from losing money.


Fast modular reduction I am looking at ways to speed up modular reduction for the polynomial

$$2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$$

I have read the paper "Generalized Mersenne numbers" by J.A. Solinas, but it does not seem to list this form of polynomial as a candidate for fast modular reduction (see section 10).

Using the definitions in that paper, this polynomial would seem to be a) proper (second largest degree is negative), b) irreducible c) has an odd constant term (-1)

Its weight is 36.

I could not find any other specific reference in the literature.

So my question is: is this a candidate for fast modular reduction using Solinas suggested method?

Other possible reference is this master thesis: https://crysp.uwaterloo.ca/software/gmnt/gmz_mcs_thesis.pdf . However, the examples and explanations appear to be drawn directly from the Paper by Solinas.

If you want to reduce integers modulo that specific prime (and I assume you have checked whether $p = 2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$ is prime or not), I would suggest you don't use the Solinas algorithms, but instead a different one geared towards modulii of the form $2^n - c$ for small $c$.

The identity underlying this operation is actually fairly simple:

$$a 2^n + b \equiv ac + b \pmod{2^n-c}$$

For you, $n=256$ and $c = 2^{32} + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1$

Here is how this would work; you take your 512 bit number $a2^n + b$ (and if you do the modulus operation immediately after each internal multiply, you never have to deal with an integer larger than 512 bits), and you compute:

$a'2^n + b' = ac + b$

This operation takes the successive words of $a$ (scanning from the lsword towards the msword), multiples each word by the 33 bit constant $c$, and adds in the corresponding word of $b$.  You call the first 256 bits of this operation $b'$ (remember, this generates results starting at the lsword), and the last 33 bits of the result $a'$.

You then do it again, taking $a'$, multiplying it by $c$ (which results in at most a 66 bit value), and adding it to $b'$.

The result of that has a small probability of being greater than $p$; check if so, and subtract $p$ if necessary.

There, you're done.  This would work fairly well on a 64 bit processor; it's less convenient on a 32 bit processor (because $c$ doesn't fit in a 32 bit word).


Why are hashes padded only at the end of the block? Cryptographic hash functions pad the input message with some indicator of length.  This is done as to avoid attacks and allows an input message of 0000 to be differentiated from 00000.  As far as I can see, padding /length inclusion invariably occurs after the message data either immediately after or right up at the end of the block.

Is there some fundamental /security reason that the length of the message can't be pre pended instead?  So it would go at the start of the first block.  Is it somehow connected with sequentially reading in files /data of unknown length?  Would it make a difference if you always knew the length of the message to be hashed?

Is it somehow connected with sequentially reading in files /data of unknown length?

Yes, indeed. It is part of a requirement to perform online message processing, or, in other words, the ability to stream the data without knowing how much data to expect.

  Would it make a difference if you always knew the length of the message to be hashed?

Well, yes, in that case you could indicate the message length in advance. Some modes of operation, such as CCM, a authenticated mode for packet encryption, rely on this kind of information. But for hash algorithms it is not required to know the message length in advance and still be secure.

Nothing prevents you to create a protocol to include the message length in advance. If you build it on top of SHA-1 or SHA-2 then this should prevent message length attacks (if implemented correctly). You'd include the message length twice that way, and would lose compatibility with software that just expect the hash.

SHA-3 is already protected against length extension attacks. Length extension attacks may not be applicable to all algorithms or situations. Length extension attacks are mainly an issue for keyed hashes. HMAC is a keyed hash which has deliberately been designed to protect against length extension attacks.


Generate key pair deterministically from a particular seed I've been reading "SQRL Secure QR Login" at Gibson's website, and I'm wondering if there is a way to generate an RSA private/public key-pair based on some cryptographically secure input, so that if the input stays the same we keep getting the same key pair on the output.

The linked web-site uses elliptic curve cryptography to achieve this property.  Is it not possible with RSA?

Of course it's possible; all you need is take your cryptographically secure input, feed it as the key to a CSRNG, and then use the CSRNG output as the source of randomness to an RSA key generation algorithm.  For a concrete example, there are several such key generation methods in FIPS 186-3, with the cryptographically secure input being the 'seed' (and you would fix all the other various parameters).

This is easy; however this is not cheap.  RSA key generation involves testing various large numbers for primality; depending on the hardware you have (and the RSA key size you are attempting to build), this can take multiple seconds.  Depending on the your requirements, this can be a deal breaker.  In contrast, the key generation method for elliptic curves is cheap; that is undoubtedly why the guys on the web-site selected it.


Shamir secret sharing: calculate rest of shares when you know secret and one share Using Shamir secret sharing, one is starting with a secret and end up with a number of shares based on a polynomial.

For example:

INPUT: secret: 123456 Shares:4 Threshhold:2

OUTPUT (4 shares calculated):

8017f1267477aa02cf0e6c6b36c29
802fd24948eab5d04fd84912dd801
8038336c5c9e4fd1c0d5157acb419
804e4486f0114ba54e7403f0cad51

My question is whether one can start with both a secret and a string - representing ultimately a share in the end state - and work his way into finding the rest of the shares?

For example:

INPUT: secret: 123456 Shares:4 Threshhold:2 Future Share: 8017f1267477aa02cf0e6c6b36c29

OUTPUT (Shares Calculated):

802fd24948eab5d04fd84912dd801
8038336c5c9e4fd1c0d5157acb419
804e4486f0114ba54e7403f0cad51

At the end you can express safely a secret in the form of shares as before - only this time you provided one of the shares as input to the process?

The benefit I see in the above process is in sharing secrets with a structure and very low entropy i.e. a Credit card number or a username. Splitting the secret in shares and sending them encrypted will still leave them vulnerable to brute force attack due to the inherent structure of the secret.

If though you:

use Diffie–Hellman key exchange for sharing 1 secret and use it as one of the future shares
produce the rest $t - 1$ shares
send the $t - 1$ shares encrypted

might this make the process more secure?

My question is whether one can start with both a secret and a string - representing ultimately a share in the end state - and work his way into finding the rest of the shares?

With $t-1$ shares and the secret, you can uniquely reconstruct the polynomial (and with that, generate all the rest of the shares, assuming you know their $x$ coordinates).  With fewer shares than that, we can't reconstruct the polynomial (even with the secret), as there'll be at least $p^k$ (where $GF(p^k)$ is the field you're working in) possible polynomials.

In essence, the secret is just another share (with $x$ coordinate 0).

However...

  Splitting the secret in shares and sending them encrypted will still leave them vulnerable to brute force attack due to the inherent structure of the secret

Nope.  You appear to be speculating that an attacker with $t-1$ shares might guess the secret, and reconstruct the other shares based on that guess.  They can certainly do that; however they have no way of determining whether that guess is correct (because all possible guesses will yield plausible looking shares).

In turns out that Shamir Secret Sharing is Informationally Secure; that is, with $t-1$ shares, you get no information about the shared secret, even if you have unbounded computation at your disposal.  This statement assumes that the polynomial was generated truly randomly; however it makes no other assumptions.


Is it possible to deduce the value of a string when given its hash and multiples hashes of the string + other known strings? To be clear, I have access to $H(S)$ and as many $H(S||K)$ as I want. Every string $K$ is known. Can I use the extra information to my advantage and try to deduce $S$, without requiring bruteforce? Or do you still have to bruteforce but try less combinations since you have more information?

Assuming the hash is strong, you will not be able to find a preimage any more easily when you know multiple hashes (whether they use the same function or another). In fact, with some hashes you will be able to derive $H(S||K)$ from just $H(S)$ and $K$ (known as the length extension attack), so it can't give you more information.

Unless the hash is broken, the only way to find $S$ in either case is to guess, hash and compare.

However, if your hash was short enough to have collisions, you could need multiple hash values to verify a guess. As an extreme example, consider the first byte truncation of a strong hash. Any guess you make will match it one 256th the time. In that case, knowing more hashes would allow you to verify your guess with higher confidence.


What is the point of using a cryptographic sequence number if you're not using it as a nonce? OSPF features the use of Auth Crypto Sequence Number however, from reading the RFC it would appear the sequence number is not being used as a nonce.

  In addition, a non-decreasing sequence number is included in
  each OSPF protocol packet to protect against replay attacks.
  This provides long term protection; however, it is still
  possible to replay an OSPF packet until the sequence number
  changes. - OSPF MD5 Authentication Draft II

Correct me if I am wrong but isn't the whole point of a cryptographic sequence number to protect against replay attacks? If so, why would you not use a nonce? Is there any benefit to this? Or is this just a weakness which was never improved upon?

I'm also struggling to make the distinction of "in the long term less of an issue" - how does that even make sense?

After reading the draft, I think that the purpose of using a sequence number in place of a nonce is because handling nonce in practical situations is very difficult. We need to keep a directory of the used nonces and then do a search through them. You can maintain a heap for the already seen nonces, but the problem is of storing them.

In the draft it says - "The value used in the sequence number is arbitrary, but two suggestions are the time of the message's creation or a simple message counter". This gives a very clear idea that the way they want sequence numbers to be used in practice is to use them in a strictly increasing fashion so that there is no need to store all the seen values and just the latest one can be stored.
I also think that using increasing sequence numbers which wrap (start to repeat) around after a decent amount of time would also work because by the time the sequence numbers repeat, the validity of the message will long be expired.


Recover key given partial key, IV and cipher text using CBC mode Given a known IV and a small part of the key (not enough to use brute force)
is there are any way to break CBC encryption with only one cipher text?

A known IV doesn't help: it's meant to be public.

Even if you know a part of the key then there's still no attack that's easier than trying all possible keys. Knowing a part of the key merely makes the set of possible keys smaller.

Knowing even a large amount of plaintext and ciphertext doesn't help to recover the key. As long as you haven't fully found the key, having access to plaintext-ciphertext pairs doesn't help recover the key more quickly. And knowing part of the key does not help to generate new valid plaintext/ciphertext pairs.

So leaking a small part of the key does not weaken the system. The problem with leaking a small part of the key is that when this happens, it's usually difficult to ensure that only a small enough part of the key is leaked, where small enough means “so that my adversaries can't brute-force the key”.

Note that, as Luis Casillas points out, here I'm assuming that the underlying block cipher is an ideal cipher, which is a good enough assumption for block ciphers that are used in practice. (Not in theory though — related key attacks do exist on AES, for example, but they're theoretical: they still require an unfeasible amount of computation). See Luis Casillas's answer for a more correct explanation.


OCB-AES: Ambiguous definition of "Encipher" in RFC document I'm implementing an OCB-AES cipher (which is described in RFC 7253), now I have to call the AES encipher function (I'll refer to that as AES-256, described in FIPS 197)

Pre-summary: I'm not sure which encipher function FIPS 197 refers to. Of course, it should be the cipher function; however, the function parameters are different.

Here's an excerpt from OCB's "associated data hash function":

   Function name:
     HASH
   Input:
     K, string of KEYLEN bits                      // Key
     A, string of any length                       // Associated data
   Output:
     Sum, string of 128 bits                       // Hash result
   Sum is defined as follows.
     //
     // Key-dependent variables
     //
     L_* = ENCIPHER(K, zeros(128))
     L_$ = double(L_*)
     ...

Another excerpt from OCB:

To be complete, the algorithms in this document require ... a blockcipher operating on 128-bit blocks...

...

ENCIPHER(K,P)  The blockcipher function mapping 128-bit plaintext block P to its corresponding ciphertext block using KEYLEN-bit [256-bit] key K.

So, I jumped to FIPS 197. Here's the cipher function:

Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
    byte state[4,Nb]
    state = in
    AddRoundKey(state, w[0, Nb-1])
    // See Sec. 5.1.4
    for round = 1 step 1 to Nr–1
        SubBytes(state)
        // See Sec. 5.1.1
        ShiftRows(state)
        // See Sec. 5.1.2
        MixColumns(state)
        // See Sec. 5.1.3
        AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
    end for
    SubBytes(state)
    ShiftRows(state)
    AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])
    out = state
end

After looking at the table  (where $1 \text{ words} = 4 \text{ bytes}$)

$$\begin{array}{|c|c|c|c|}& \text{Key length }(Nk \text{ words)} & \text{Block size } (Nb \text{ words)} & \text{Number of rounds }(Nr)\\\text{AES }128&4&4&10 \\\text{AES }192&6&4&12\\\text{AES }256&8&4&14\end{array}$$

Paraphrasing only the input parameters for $256$:

void cipher(char in[16], char w[240]);

Here's the main point: The first excerpt wants me to call AES-256 cipher with 1) the key 2) zeros of 16 bytes. How can I pass the 256-bit key and 128-bit zero? One parameter has $240$ bytes and the other has $16$? Is my "function prototype" for the cipher wrong, or do I need to use key expansion, etc..., somehow?

The 256-bit K of OCS-AES must first go thru FIPS 197's

  KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)

where it is key[4*Nk] to be transformed into w[Nb*(Nr+1)] (32×4×(14+1) = 1920-bit), which is the last input of

  Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])


Addition / Multiplication modulo 13 I am currently studying Diffie-Helman protocol. In my lecture notes I have a generator g=2 and I'm in group $Z_{13}^*$ . There I calculate a remainder cycle from 1 to 12 with $r =g^i \mod 13  \forall i [0,12]$

I do not quite understand the relation between the generator and the group. This is my $Z_{13}^*$:

How is the generator in the multiplication group any different from $Z_{13}^+$?

$\mathbb{Z}^*_{13}$ is a group with 12 elements, not 13.

A group is defined by a set of elements, and a "law". The law combines two elements and yields a third one within the set. You get a group if the law fulfils some properties (the law is associative, there is a neutral element, each element has an opposite in the group).

$\mathbb{Z}_{13}$ is a group with 13 elements, using "addition modulo 13" as group law. The neutral element is $0$; the opposite of $4$ is $9$ (because $4 + 9 = 13 = 0 \mod 13$).

$\mathbb{Z}^*_{13}$ is a group that uses "multiplication modulo 13" as group law; it contains all the elements that are invertible modulo 13. Since 13 is prime, these are all elements of $\mathbb{Z}_{13}$ except $0$; so you get 12 elements (the integers $1$, $2$,... $12$ modulo $13$). The neutral element is $1$ (multiplying any element by $1$ leaves it unchanged). The opposite (traditionally called "inverse" since the law is called "multiplication") of $4$ is $10$ (because $4\times 10 = 40 = 1 \mod 13$).

A generator for a group is an element $g$ such that applying the law repeatedly on it ultimately yields all the group elements. In $\mathbb{Z}^*_{13}$, $2$ is a generator for the whole group: if you multiply $2$ by $2$ then you get $4$; if you multiply $4$ by $2$ you get $8$; multiply by $2$ again and you get $3$; then $6$, $12$, $11$, $9$, $5$, $10$, $7$, then $1$. You got all 12 elements. On the other hand, $8$ is not a generator for the whole group since it generates only $8$, $12$, $5$ and $1$.


Schnorr groups allowing fast modular reduction, vs GNFS I'm looking for Schnorr groups allowing fast modular reduction. Say, using the notation in DSA, with 256-bit prime $q$ and 3072-bit prime $p$, and $p\equiv1\pmod q$.
Are there standards, RFC, or other references about this?
I'm considering choosing $p$ with all bits at $1$, except for a relatively short segment not too far from the top bits. That allows very fast Montgomery modular reduction, which can next to halve the computational effort compared to arbitrary $p$. Would that make GNFS faster, by allowing selection of a better polynomial?
Any reason not to use $g=2^{(p-1)/q}$, which seems a most natural generator?
A rather extreme example of what I have in mind:
$$\begin{align}
q&=2^{256}-2^{194}-1\\
p&=2^{3072}-1\\&\quad-2^{2745}\,\mathtt{2219c36803ffffff6352c900000000006008ef007fffffffbcc79fd201_h}\\
\end{align}$$
q=fffffffffffffffbffffffffffffffffffffffffffffffffffffffffffffffff
p=fffffffffffffffffe000000443386d007fffffec6a5920000000000c011de00ffffffff798f3fa401ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

where $q$ is the smallest $256$-bit prime with a single $0$ bit; $2745$ is chosen to minimize the bit size of the $230$-bit constant defining $p$, happens to put that term in the high-order bits of $p$, and (due to the special form of $q$) also creates long sequences of $0$ and $1$ in that segment of $p$.
Update: Daniel Shiu's answer shows that indeed, the above allows a sizable speedup of GNFS. Let's forget about it. What about taking $p=2^{3072}-1-c\,2^{3072-\ell}$ where $c$ is a $\ell-1$-bit nothing-up-my-sleeves constant, and some larger $\ell>230$? Up to $\ell$ about $1024$ (one third the bit size of $p$), we still save most of the modular reduction effort.

TL;DR

There are no standards or RFCs that use this idea.
There is a slightly improved number field sieve attack on your example number based on back of the envelope calculations (see below).
Your proposed generator would be fine.
The follow on proposal should not admit special polynomials for $\ell\ge 768$.

The back-of-the-envelope generic attack
To attack a general 3072-bit prime number, one could use the method of Joux and Lercier to construct polynomials $f_\alpha(x)$ and $f_\beta(x)$ with a common root modulo $p$. A good choice seems to be $f_\alpha$ of degree 5 and coefficients 0,+1,-1 and $f_\beta$ of degree 4 and coefficients around 614-bits. One can then test $\mathcal N(a+b\alpha)$ and $\mathcal N(a+b\beta)$ for $0\le |a|,b\le 2^{65.5}$ for both being $2^{65.5}$ smooth (here $\mathcal N$ denotes the norm down to $\mathbb Q$). The largest numbers would be roughly, 327.5-bit and 876-bits and a quick Dickman-$\rho$ calculation in SageMath says that there's a $2^{-65.332}$ chance of them both being smooth and you should be able to get more smooth numbers than primes below the smoothness bound. You then solve a roughly $2\times\pi(2^{65.5})$ variable sparse linear algebra problem (where $\pi(n)$ denotes the number of primes up to $n$) and then and subsequent problem are significantly less work. The work of $2^{131}$ smoothness tests and the large linear algebra problem are not totally out of whack with the usually quoted 128-bits of work.
The back-of-the-envelope for your prime
Your prime admits the polynomial pair
$$f_\alpha(x)=x^9-2^{15}cx^8-64$$
$$f_\beta(x)=x-2^{342}$$
where $c$ is your 230-bit constant. One can then test $\mathcal N(a+b\alpha)$ and $\mathcal N(a+b\beta)$ for $0\le |a|\le 2^{46.5}$ and $0<b\le 2^{76.5}$ for both being $2^{61.5}$ smooth. The largest numbers would be roughly, 693.5-bit and 418.5-bits and SageMath says that there's a $2^{-61.197}$ chance of them both being smooth. Thus again you should be able to get more smooth numbers than primes below the smoothness bound. You then have a roughly $2\times\pi(2^{61.5})$ variable sparse linear algebra problem etc. This is roughly $2^{123}$ smoothness tests and a commensurable linear algebra problem. Your problem is therefore perhaps 8-bits easier than a typical 3072-bit prime. This is much less degradation than other SNFS attacks, and might be tolerable depending on circumstances.
ETA: In re the follow up question. The smallest degree for which special polynomials could beat the J-L pair seems to be 4. A generic blob of 768 or more bits at the head of your 3072-bit number should mean that there is no special polynomial of degree 4 or more. Taking $\ell<768$ might still be secure in some cases, but the analysis starts getting fiddly.


AES s-box representation I have seen in various papers like in this one page 4, that the AES s-box equation is:

$S=A \circ φ^{-1}(φ(x)^{254})$ where $φ$ is the isomorphism from $\mathbb{F}_2^{8}$ to $\mathbb{F}_{2^{8}}$ with its basis and the reduction polynomial and $A$ is the affine transformation defined in AES.

I am kind of new to this area, but what I would say is that $φ(x)^{254}$ is the inverse of $φ(x)$ since their multiplication generates the $φ(x)^{255}$. The degree with the reduction polynomial is 255 right? (Since it's irreducible, but I am not sure if we should include zero as well)

So, what I would expect is:

$S=A \circ φ(x)^{254}$

How did the first equation come up?

The tricky point is that $\mathbb{F}_2^8$ is not a field; it is a degree-8 vector space. Multiplications are not defined on vector spaces. However, the $A$ transform is defined only on the vector space, not on the field (it is "affine" only when considering its source/destination space as a vector space).

The $\phi$ and $\phi^{-1}$ operations are thus "type conversions". If you think of it in terms of implementations, they are akin to type casts: if $x$ is a vector, then $\phi(x)$ is the same sequence of bits, but interpreted as a field element. So you have to apply $\phi$ (i.e. switch to field interpretation) in order to do field-related things (here, exponentiation), then $\phi^{-1}$ must be apply on the result to go back to vector space interpretation, so that a vector space affine transform ($A$) may be applied.

A possible source of confusion is the notation $\phi^{-1}$ that means "the inverse function" (i.e. the one that goes in the reverse direction), but not "the inverse of the value". The same term ("inverse") and the same notation (exponentiation with $-1$) are used for two very different things.

Also, $z^{254}$ indeed computes the inverse of $z$ in the field $\mathbb{F}_{2^8}$, but it also returns 0 when the source value is 0, which is what we want in AES, while the inverse of 0 is nominally not defined. Hence the use of exponentiation in the formula, instead of inversion.


Why does HOTP use such a complex truncate function? In the HOTP protocol after calculating a 20 byte hash it is truncated to 4 bytes.

For this first an offset is calculated (low-order 4 bits of the last byte) which determines the four bytes to be selected:

DT(String) // String = String[0]...String[19]
 Let OffsetBits be the low-order 4 bits of String[19]
 Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15
 Let P = String[OffSet]...String[OffSet+3]
 Return the Last 31 bits of P

Why is this more 'secure' than simply always taking the first four bytes of the hash?

It looks to me that the original intent was to make sure that all bits of the hash digest have an equal chance to contribute to the truncated portion.  But one of the properties of a secure hash function is to ensure that a single bit change results in a cascade that yields changing bits across the entire digest.  If you don't trust this property in the hash algorithm, you either have a very weak hash algorithm or a weak understanding of the properties that make a hash algorithm strong.

If any of the input bits to the hash differed originally, at least some of bits in the last four bytes will reflect it, with the expected reduction in collision resistance from $2^{80}$  to $2^{16}$.

So, given a good hash algorithm, it's not "more secure".  At best, it's equally secure.  In the real world, it's slightly more risky (and therefore less secure) because the added complexity offers the chance for a programmer to make an implementation mistake.


How to properly apply the AES Mixcolums? I had searched a lot but I don't undestand how work the operation on binary (How to solve MixColumns). What I don't undestand is from where he catch 0001 1011 to do the XOR operation.

Can someone explain me? Thanks in advance for the replies.

Do you mean where we come up with 0001 1011 (also known as 0x1B)?  That's actually mentioned in the answer:

  Multiplying by $2$ is what your question is about: it is equivalent to shifting the number left by one, and then exclusiving-or'ing the value 0x1B if the high bit had been one (where, in case you're wondering, the value 0x1B came from the field representation)

That is, the $GF(2^8)$ representation that AES uses is a polynomial representation, based on the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$; 0001 1011 (or 0x1B) are the lower 8 bits of that polynomial.

If you don't understand that, well, just assume that 0x1B is a magic value that just happens to make things work...


Somewhat Homomorphic Encryption versus Fully Homomorphic Encryption? Is that correct that Somewhat Homomorphic Encryption is more efficient that “Fully Homomorphic Encryption” (FHE) but less efficient than Partially Homomorphic Encryption (e.g Paillier encryption)?
Is that correct that in Somewhat Homomorphic Encryption (e.g. used in Private Database Queries Using Somewhat Homomorphic Encryption (PDF)), the plaintext can be defined over a “known finite field”, so after homomorphic operations – when we decrypt – the plaintext is in that finite field?

PHE (partially homomorphic encryption) schemes are in general more efficient than SHE and FHE, mainly because they are homomorphic w.r.t to only one type of operation: addition or multiplication.

SHE is more general than PHE in the sense that it supports homomorphic operations with additions and multiplications. The drawback is that you can perform only a limited number hom. operations.

To answer your first question, a SHE scheme is also a PHE. This implies that PHE's are at least as efficient as SHE's.

FHE allows you to do an unbounded number of hom. operations by bootstrapping. This step can only be done (currently) by evaluating the decryption circuit inside a SHE scheme.

AFAIK, all plaintext / ciphertext operations are done within a known modulus. The only unknown thing should be the secret key. See a construction example here: DGHV Scheme.


Zero padded signatures in the Bleichenbacher attack I'm studying this attack and i have some doubts about it; let me explain with an example.

Here is my decoded signature:

00 01 FF .. FF .. 00 ASN1 HASH

I forge a decoded signature like this:

00 01 FF .. FF .. 00 AS1 HASH GARBAGE

and than I calculate the cube root in order to obtain the RSA encoded signature.

The cube root resulted from this attack has always a number of bytes lesser than the signature key (for example, RSA1024=128bytes) though. A signature properly padded has always 128bytes.

Why does RSA accept a 0x00 padded cube root as encoded signature? Couldn't a check like this (leftmost bytes != 0x00) be used to avoid this type of attack?

Why does RSA accept a 0x00 padded cube root as encoded signature?

It is not correct to assume that a valid RSA signature always starts with a byte containing a few bits set to one.

An RSA signature is calculated by padding the hash value. The padded hash value is then raised by the private exponent using modular exponentiation. The modular exponentiation of the value will return a value that is between zero and the modulus. Each of the signature values between these numbers is about equally likely.

That also means that a significant amount of signatures have fewer than $n - 8$ bits when encoded as unsigned big endian integer. It depends on the value of the modulus, but you would expect about 1 in 192 to be smaller than $n - 8$ bits overall. Here $n$ is the number of bits that the modulus occupies; for RSA this is also the key size - this answer assumed that $n$ is a multiple of 8, e.g. 1024 in the question.

The I2OSP function in RSA PKCS#1 will however make sure that all signature values are left-padded with zero-valued bytes until signatures have the same size as the modulus. So signatures that start with 00-valued bytes are valid by definition.

  Couldn't a check like this (leftmost bytes != 0x00) be used to avoid this type of attack?

So, in conclusion, no, because your check would reject perfectly valid signatures.

The only check that can be meaningfully be performed before signature verification is to match the signature size (including zero bytes) to the key size.


Why does md5_crypt move bytes around? I looked into the code for md5_crypt the other day (yes, I know it's insecure), and I noticed that after mushing up everything with strange md5 hashes, it generates a base64 string with a strange order of bytes. You can see that either in the FreeBSD implementation lines 144-155 or in passlib which calls this function.

Why do they do that?

One of the candidate answers you should consider is "for no good reason."  As Provos and Mazières put it in the bcrypt USENIX paper (section 6.1.2):

  Some steps in the algorithm make it doubtful that the scheme was designed from a cryptographic point of view—for instance, the binary representation of the password length at some point determines which data is hashed, for every zero bit the first byte of the password and for every set bit the first byte of a previous hash computation.

That's remarking on a different step of the algorithm than you are, but I suspect it generalizes to the step you highlight as well.  Any halfway decent hash function is going to diffuse its state, and MD5 is no exception, so shuffling the bits of the MD5 output is just suspect.

PHK wrote a history of md5crypt that might be of some use to help us understand his mindset at the time, although it doesn't very much go into nuts and bolts, so it doesn't particularly illuminate the step in question.


Diffie-Hellman Private Key Size I'm currently writing my own implementation of Diffie-Hellma n(This isn't for actual use. This is strictly for me to get a better understanding of DH by doing it myself.)
For the prime and generator, I am using RFC 3526, more specifically the 4096-bit prime.
My question is, is there a specific standard secret integer generation for Diffie-Hellman? Since the security of the secret integers(Commonly two, but DH does support more than 1-1 communication) is pretty crucial to the security of the key exchange.

DHKE
In an exponential Diffie-Hellman, denoted by DHKE, one takes a group $G$ with a generator $g$ with its order $n$.
The Alice and Bob, during the key exchange, generates random number $a$ and $b$ in the range $a,b\in (1,n)$ and transmits $g^a$ and $g^b$ and finally, they establish the key as $g^{ab}$ then use a KDF to derive a symmetric key and IV/nonce.
There is also Elliptic Curve version of DHKE and it is denoted by ECDH and it is more used than the classical exponential version.
Prime
In DHKE, we choose prime to be a safe prime, that is $p = 2 \cdot q + 1$ with $q$ is also a prime. The $q$ is called a Sophie Germain prime.
This is a countermeasure against Pohlig-Hellman algorithm that benefits from the small factor of the $p-1$. If a safe prime is used than the factors are $2$ and $q$. Having a large factor is a countermeasure against the Pohlig-Hellman.
There is also Schnorr group with $p = r\,q + 1$. This can be considered as a generalization of the sage primes. The sage prime is optimal.
Prime Generating
The naive approach generates a prime $q$ then check for the primality of $2 \, q +1$ (Menezes:  Algorithm 4.86). In pseudocode;
do
   p = randomPrime(k-bit integer)
while ((p − 1)/2 is composite)

There are faster methods

Double-Speed Safe Prime Generation by David Naccache, 2003
as the title suggests, this speed this up by about a factor of two by testing both $2q + 1$ and $(q − 1)/2$ for primality.
The idea is using the random prime $p$ as safe prime or Sophie Germain prime;
do
  p = randomPrime(k-bit integer)
while ((p − 1)/2 and 2p + 1 are composite)

Safe Prime Generation with a Combined Sieve by Michael J. Wiener, 2003.
They proposed sieving small primes up to $2^{16}$. This provides $15x$ speed up than the naive algorithm.
The idea starts with this observation; both $q$ and $q=2p+1$ must be congruent to $2$ modulo $3$. Therefore one can eliminate the candidates with which are $0$ modulo $3$ and $1$ modulo $3$.
This can be generalized to any odd prime $r$. Eliminate $q$'s that are conguruent to $(r-1)/2$ modulo $r$ since in this case $p$ is divisible $r$.
Take a set $S$ all odd prime $<B$. Then $\prod_{r\in S}(r-2)/r$ of the candidates will survive the sieve.
If $B=2^{16}$ it is estimated that it can produce $\approx \times 15$ speed up.

Collision
Now we will look at the probability of arriving the same random number if there are $k$ people using the same DHKE modulus. We are assuming that the $k$ people using the same secure (unpredictable) random number generator to generate their random keys. To simplify this, we can assume that there is one person who generates random numbers. In this case, this is completely the birthday-paradox and in Cryptography we look at this is the birthday attack to find a collision with 50%. This is a common way to look at the collision of the hash functions.
Let $H$ be the range of the random number generator, and the $p$ represents the probability we want, then $n(p; H)$ be the smallest number of values we have to choose;
$$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$$
In the classic hash collision case, we set $p=1/2$ and this approaches
$$n(0.5;H) \approx 1.1774 \sqrt H$$ and we usually represent as $\mathcal{O}(\sqrt{H})$
Now, let's look at some actual numbers.

2048-bit prime
Assume that $n$ is 2048-bit number, remember $n$ was the order of the generator $g$. Then
$$n(p;2^{2048})\approx \sqrt{2\cdot 2^{2048}\ln\frac{1}{1-p}}$$
With 50% probability $$n(0.5;2^{2048})\approx 2^{1204}$$
As a result, you need to generate $2^{1204}$ random numbers to hit one again with 50%. Not feasible.

4096- bit prime
$$n(p;2^{4096})\approx \sqrt{2\cdot 2^{4096}\ln\frac{1}{1-p}}$$
With 50% probability $$n(0.5;2^{4096})\approx 2^{2048}$$
As a result, you need to generate $2^{2048}$ random numbers to hit one again with 50%. Not feasible.
Pre-Compute the dlog table.

Since the modulus are pre-determined by the standards, one can argue that some organizations with superpowers built some DLog table for the modulus.
This is not a danger, too. Let assume that they can build a table up to $2^{64}$ then the probability of your random hit is $$\frac{\ell \, 2^{64}}{2^{2048}}$$ with $\ell$ try. Put the possible key generation number of your group into $\ell$. So, 2048-bit is a really big number to deal with.


Server authentication in TLS 1.2 with static DH For (EC)DHE cipher suites, server authenticates itself by proving the possession of the private key matching its certificate by signing ServerKeyExchange message (link):
  struct {
      select (KeyExchangeAlgorithm) {
          case dh_anon:
              ServerDHParams params;
          case dhe_dss:
          case dhe_rsa:
              ServerDHParams params;
              digitally-signed struct {
                  opaque client_random[32];
                  opaque server_random[32];
                  ServerDHParams params;
              } signed_params;
          case rsa:
          case dh_dss:
          case dh_rsa:
              struct {} ;
             /* message is omitted for rsa, dh_dss, and dh_rsa */
          /* may be extended, e.g., for ECDH -- see [TLSECC] */
      };
  } ServerKeyExchange;

For RSA cipher suites, server authenticates itself by proving the possession of the private key matching its certificate by decrypting pre-master secret sent by client in ClientKeyExchange message (link):
struct {
    select (KeyExchangeAlgorithm) {
        case rsa:
            EncryptedPreMasterSecret;
        case dhe_dss:
        case dhe_rsa:
        case dh_dss:
        case dh_rsa:
        case dh_anon:
            ClientDiffieHellmanPublic;
    } exchange_keys;
} ClientKeyExchange;

How does the server authenticate itself and prove possession of the private key matching its cert for static DH? It won't send ServerKeyExchange, because its public key embedded in its certificate already contains relevant info. Client won't send ClientKeyExchange with EncryptedPreMasterSecret, because this is not RSA.
Does the server prove possession of the private key solely by being able to arrive at the same master secret as the client?

Yes -- which is the same as RSA, because there the server proves it was able to decrypt the premaster secret (with the private key) only by getting the correct master secret, and working keys, and thus Finished. (All of these are the same for 1.1 and 1.0, and SSL3.)


Can an attacker exploit the nonuniform distribution of letters in a diceware password to improve a brute force search? I use some diceware pass phrases in some places but I have one question that I can't find the answer to.

Let's say I roll the dice and get $N$ words with a total of $M$ letters and that I don't put spaces in between the words.

An attacker wishing to brute force my secret could have to try $7776^N$ times to break it as a diceware pass phrase OR $26^M$ to break it as a "normal" password (assuming I get only words with letters).

But the attacker trying to break it as a normal password could assume that it is made up of English words and then they'd know that some letters and combinations of letters are more common.

So my $M$ letters will not have the entropy of letters selected at random but some lower entropy.

My question is, what $M$ do I need to make up the same entropy as the $N$ words?

But the attacker trying to break it as a normal password could assume that it is made up of English words and then they'd know that some letters and combinations of letters are more common.

They could try this, but they would be stupid to try this, because there are many fewer $N$-word diceware passwords than $M$-letter strings of English letters of the same length as an $N$-word diceware password!

Suppose you use a ten-word diceware password.  There are $7776^{10} \approx 8 \times 10^{38} \approx 2^{129.2}$ such passwords.  This is already a larger haystack than any adversary can find a single needle in.  (If passwords are hashed without salt, an extremely powerful adversary may be able to find one of many needles in a haystack that big, but you could pick $N = 20$ instead, and the service oughta salt their password hashes.)

Any distribution on sequences of $M$ independent English letters that covers more possibilities than these $7776^{10}$ diceware passwords is an even larger haystack to search for a needle in.

A smart adversary, who knows all the details of your method and just doesn't know the password you chose by that method, won't give themselves a larger haystack to search in.  A stupid adversary who does give themselves a larger haystack to search in will just waste more time searching!

For example, the distribution on $M$ independent English letters following the usual letter frequencies in English would give relatively high probability to sequences like aoqothropaaeeaetphtticawglesttgeectoyheldshnfznecr which has a lot of e's and t's and a's but not many z's, x's, q's, etc.  This is not a possible diceware password, however, even though it has the same length as a ten-word diceware password with five letters per word.  And it would give lower probability to woozydizzybuzzyfuzzyjazzymezzoexxonpizzapyrexvixen, which (with an appropriate word list) is a possible diceware password.

Let's work through a simplified example.  We'll use a dictionary of five words: cat, car, act, art, and rat.  We'll pick a single word uniformly at random from the dictionary, so that each word has equal probability 1/5, with just over two bits of entropy.

The corpus in this dictionary has letter frequencies a 5/15, c 3/15, r 3/15, t 4/15, under which distribution each letter position has under two bits of entropy.  There are $4^3 = 64$ possible three-letter words from this alphabet, of which the vast majority, 59, aren't in our dictionary.

An adversary trying to guess our password from the dictionary has a $1/5 = 20\%$ chance, of getting it right in a single trial.

This is the smartest, most efficient adversary.
An adversary trying to guess our password from the letter frequencies independently has a $\frac{1}{5}\cdot\frac{19}{225} = 19/1125 \approx 1.7\%$ chance of getting it right in a single trial.

Why?  The distribution on three-letter passwords is the product of the letter probabilities in this model.  If the adversary guesses a word in our dictionary this way, there's a 1/5 chance that it's the right password, but there's only a $19/225 \approx 8.5\%$ chance that the word the adversary guessed with these letter probabilities is in our dictionary.  With probability $206/225 \approx 91.5\%$, the adversary will be guessing passwords that you would never have chosen: they're wasting most of their time barking up the wrong trees in a much larger haystack.

This is the adversary who takes advantage of the per-letter entropy as you described.  Even if they sort by probability rather than choosing randomly, they'll first try aaa, then aac, then aat, aca, etc., wasting time on impossible passwords.  Even if every word in the dictionary happened to come first in this ordering, this adversary has no better chance than adversary (1).
An adversary trying to guess our password from the letters, ignoring the frequencies, has a $1/64 \approx 1.5\%$ chance of getting it right in a single trial.

Why?  Under this distribution, every letter has equal probability 1/4 independently, so every three-letter word has equal probability $(1/4)^3 = 1/64$, including the one we chose.  With probability $59/64 \approx 92\%$, the adversary will be guessing passwords that you would never have chosen.  They're also rummaging through a much larger haystack, but they're doing it even less efficiently than adversary (2).

This adversary just tries all combinations without regard to letter frequency.  As you can see, this adversary is slightly worse at the job than adversary (2), so knowledge of the letter frequencies helps a little bit, but they're both much worse at the job than adversary (1).

Every word you add, if drawn independently, multiplies these probabilities: pick a second word independently from the same dictionary, and adversary (1) now has $(1/25)^2 = 1/25 = 4\%$ chance of success, adversary (2) now has $(19/1125)^2 = 361/1265625 \approx .029\%$  chance of success, and adversary (3) now has $(1/64)^2 = 1/4096 \approx .024\%$ chance of success.  If you make the dictionary large enough and the sequence of words long enough that you defeat the smart adversary (1), then you also defeat the stupid adversaries (2) and (3).

  My question is, what $M$ do I need to make up the same entropy as the $N$ words?

Don't worry about $M$.  Pick $N = 10$ for diceware and you're all set.


Signature scheme with two private keys, neither derivable from the other Is there any scheme, ideally one widely used or at least widely available, where you can treat both the signing and verifying keys as secret?

Basically, the functionality I'm looking for is this:

You derive two keys, $S$ and $V$.
$S$ cannot be derived from $V$, nor can $V$ be derived from $S$.
A signature can be made with only $S$ and verified with only $V$.
$S$ has no special structure. That is, it is not easy to tell if a given string is a valid $S$ or not.

The intended application is authentication. The idea is that either the user or the server would generate the two keys. The server would store $V$, and either the user or the server would store $S$ encrypted with a passphrase. An attacker with only the encrypted $S$ would not be able to launch an offline attack to decrypt it because he'd have no way to tell if his decryption was valid other than asking the server. And, if the server was compromised, an attacker still couldn't impersonate a client because he can't derive $S$ without breaking the passphrase.

Well, one obvious way to do this would be using RSA with a large 'public' exponent.  That is, it is the traditional RSA sign/verify operation except that, instead of the usual optimization of having a small 'e' value, you would have a large one (a bit smaller than the modulus); and then derive d from e, p and q in the usual manner.

As for the requirement that it has no special structure, the only special structure that either exponent has is that they are odd; any odd value is a potential exponent (note: to avoid biases, it may be advisable to, when generating the p and q values, you exclude values where p-1 (and q-1) have small odd factors).

So, the signing key S would be the value (d-1)/2, and the verification key would be the value (e-1)/2, with the modulus being treated as public data (that is, there is no need to encrypt it).  That this is secure (and you can't derive one from the other) follows directly from the standard RSA assumptions. That it meets requirement 4 follows from the idea that (d-1)/2 can take on any integer value.


applying HKDF at both the client and the server I have two keys (K1 and K2) at both the client and the server. I hope to use HKDF in both client and server side to concatenate the keys.
I will use the same salt value at both the client ad the server. Then will I be able to arrive at the same key by applying HKDF at both the client and the server to K1 and K2?

HKDF is deterministic, that is, given the same input; IKM (Input Keying Material), salt, and contextual info (these last two are optional, but recommended), and provided that the same underlying hash function is used (SHA256, for example), the output will always be the same.


Why is AES-SIV not used, but AESKW, AKW1? I'm trying to investigate different key wrapping algorithms for my implementation. I've noticed that AES-SIV is very rarely implemented by most of open source libraries. Most of them implements key wrap from RFC 3394.

It's a bit weird, as AES-SIV has many nice properties and (maybe I'm wrong) seems like best choice for key wrapping in most cases. So I wonder if I haven't missed something. Are there any known weaknesses of AES-SIV?

No, AES-SIV is just newer. There are currently no published weaknesses (to my knowledge).

There are however a few practical inefficiencies:

the fixed locations of the SIV (/ authentication tag) can be a bit tricky to work with, as it means that the wrapped key data cannot be stored in the same place as the unwrapped key data;
it's a two pass protocol, which requires a bit more work.

The other wrapping methods have been standardized as well and are not broken in any significant way. So there is no big incentive to shift to SIV, even if it has the deterministic integrity protection property.

Many keys are stored in key stores rather than being wrapped individually (although combined approaches are used as well). A key store is likely to have no need for a deterministic algorithm such as SIV.

So it's an educated guess that AES-SIV is not implemented much due to lack of (commercial) interest.

Note that we're still in the process of moving out SHA-1 in favor of SHA-256. There is a very clear reason to do so, and SHA-3 is already out as well. The security field is not known for speedy transitions, even though it is just half a century old.

EDIT > 2yrs later: currently there seems to be a bit more interest to avoid the dire consequences of IV reuse for CTR mode and all authenticated ciphers (CCM, GCM, EAX etc.) that rely on it. That may speedup the use of AES-SIV and it's sibling, AES-GCM-SIV.


Does maximum length of CN in a x509 cert include the length of the OIDs? This is a CN from a x509 certificate (I have done some substitutions just to mask the data but the length is not changed)

CN=Alex Perry/pseudonym=88b2e76beE0e4e4b94b502020202262E/x500UniqueIdentifier=22e4EE844E8B744490EEE96EE8BEB7E29548e4496E425247944B025E04528654/postalCode=60601

As per the RFC, the CN field should not be more than 64 bytes, but this CN is more than 64 bytes

So does the max length 64 only counted up for the CN=Alex Perry & the rest of the string (/pseudonym, /x500UniqueIdentifier etc) is ignored?

If so, is there a limit imposed on the total maximum length? What is that?

They are separate fields. Their lengths, from the very same RFC:

ub-pseudonym INTEGER ::= 128

ub-postal-code-length INTEGER ::= 16

If x500UniqueIdentifier is OID 2.5.4.45 then it is a bit-string which isn't constrained in length (afaik).

Both the Subject and the Issuer fields are instances of RelativeDistinguishedName (section 4.1.2.4) and are of SIZE (1..MAX)

Appendix B says that:

  MAX indicates that the upper bound is unspecified.    Implementations
  are free to choose an upper bound that suits their    environment.

So while the definition suggests that Subject can be as large as you want it to be, it also suggests that it may well be constrained by your particular implementation.


Is it enough to encrypt then sign when using symmetric-key encryption? I'm doing some tests in Java, encrypting messages exchanged between two entities. I'm using a symmetric key to encrypt the messages.

Right now I've stumbled upon a question. Is it enough to encrypt then sign when using symmetric-key encryption? The signature process is based on an asymmetric key pair. I think that by encrypting the message the content will be hidden and then if I sign it it will be authenticated but I feel like something is off. I'd like to hear someone else's opinion on this topic since I'm nothing but a beginner trying to learn.

Well, it would depend somewhat on what your security goals are, but signing the message would enable the receiver to verify integrity: that the ciphertext that it got is precisely the ciphertext that the sender sent (at some point; you still may need to worry about replay).

However, you're assuming that you have a shared symmetric key to encrypt; is there a specific reason you don't use that to also perform integrity (either by using a combined mode operation, such as AES-GCM, or generating a Message Authentication Code using other key bits that you shared).  The one thing that using a signature buys you is the ability to prove to a third party that the message is authentic (and not something the receiver made up); is that important to you?


Is it possible to find data which makes sense when decrypted with different keys? In theory, does a piece of data exist which, when encrypted (using any method) with a given key, makes some sense when decrypted with the wrong key?

Here, a definition of "some sense" might be something like "when interpreted as ASCII character codes, the data forms a series of mostly correctly spelled English words". In essence, a definition of "some sense" would be that the decrypted data looks (almost) like it was correctly decrypted.

Yes. How to find such data depends on which encryption you are using. With one time pads it's trivial: You can freely choose another pad that when used as a key will decrypt the ciphertext to an arbitrary message (of proper length).


How to account for moore's law in estimating time-to-crack? It seems to be common practice (at least in some communities) to tack on the phrase "with current computing power" when estimating the absurdly long time it would take to, for example, brute-force an ECDSA private key or find an SHA256 collision, but am I wrong in thinking that these calculations should account for the ever-increasing power of the "average" computer?

In short, when making an educated guess of time-to-crack via brute force, is there a some kind of easy "fudge factor" to include that accounts for likely technological improvements a la Moore's Law (et al)?

Moore's law has several variants. Gordon Moore himself first put it as a double of transistor density every year (i.e. you could put twice as many transistors on a given wafer surface, and production cost increases linearly with the wafer surface). In 1975, Moore altered his law to a double every two years. However, putting more transistors in a given surface also entails making them smaller and closer to each other, and this allows for clocking them at higher rates, too. So the "classical" version of Moore's law is "double performance every 18 months".

Performance depends on the kind of task you are trying to perform. For a general purpose computer, having more transistors does not makes things really better beyond a given point -- if you want to add "real-life" values which fit in 32 bits, then having 64-bit registers will not give you a boost. At some point, "many transistors" turns into "several cores", which helps a lot if (and only if) the task at hand is amenable to parallelism.

For symmetric cryptography, we usually worry about exhaustive search. The cost-effective attacker will use FPGA or ASIC. Parallelism is a given, so the attacker benefits from advances in both transistor density and clock rates. However, for the truly massive attack jobs, energy consumption (and its offspring heat dissipation) becomes a bottleneck, and higher clock rates do not help for that. So you can consider Moore's law to amount to about "1 bit per year" (a 100-bit key is as robust now as a 120-bit key will be in 20 years).

For elliptic curves, the most efficient attack is discrete logarithm using the "generic" algorithms, which work in $O(\sqrt{N})$ for a curve of size $N$. This means that a 256-bit curve fares about as well as a 128-bit symmetric key. Moore's law, then, yields "2 bits per year" of computing power to the attacker.

For integer factorization and classical discrete logarithm (i.e. RSA, DSA, Diffie-Hellman, ElGamal... but not the EC variants thereof), things are more complex. The best known algorithms are subexponential (that's the General Number Field Sieve); but their implementation requires large amounts of fast RAM. RAM size increases with transistor density as per Moore's law, but RAM latency does not get better as fast as that. In fact, base RAM latency is more or less stalled in recent computers. Therefore, it is difficult to give even a rough estimate of Moore's law effect on RSA security.

To account for Moore's law, several individuals and organizations have published estimates of key strength, as "recommendations" for minimal key length, now and in the next few decades. These recommendations vary quite widely from each other; there is a nice summary (with online calculators) on this site. The recommendations always use worst case estimates: they do not want to predict the actual attack cost, they aim at presenting key sizes which are "large enough" to thwart attacks. Therefore, each figure is a mixture of attack cost estimates, and a more or less generous amount of paranoia. For instance, NIST recommends not using 1024-bit RSA keys since last year, and yet the current RSA-breaking record is 768 bits, are it is known right now (2012) that existing academic resources are far from being sufficient to attack a 1024-bit RSA key.

As a very crude but effective estimate: 112-bit symmetric keys, 224-bit elliptic curves, and 2048-bit RSA/DSA/DH keys, ought to be enough for the next two decades (at least).


What does it mean for a number to be “in the order of” a prime number? In some papers I'm looking at there is some language that says things like "Choose a random number in the order of prime q" and I see some syntax that it is referring to that looks s = Zq (where q is a subscript). What does it mean for a number to be "in the order of" some prime?

For context, the paper I am reading is The Twin Diffie-Hellman Problem and Applications.

Here is a link to the paper: https://eprint.iacr.org/2008/067.pdf

You are (slightly) misreading the statements. I've checked through all 13 occurrences of the word "order" in that paper, and see only "typical" statements, such as:

  Let $\mathbb{G}$ be a group of prime order $q$

"Order" means one of two things in group theory:

The order of a group is just the number of elements in it. So a group of prime order $q$ is just a group $\mathbb{G}$ where $|\mathbb{G}| = q$.
The order of an element of a group $g\in\mathbb{G}$ is how many times you have to repeat the group operation of $g$ to get to the identity. For a group written additively, it's the smallest $n$ such that $ng = 0$. For a group written multiplicatively, its the smallest $n$ such that $g^n = 1$.

These are (sort of) connected by a result in group theory that says that $\forall g\in\mathbb{G}, g^{|\mathbb{G}|} = 1$. As a consequence, the order of an element always divides the order of the group.
This is a generalization of both Fermat's little theorem and Euler's theorem.

The paper you're reading only seems to use order to mean the first of these two things. Note that groups of prime order are special in that they're always cyclic groups.
The most basic example of a cyclic group is $\mathbb{Z}/p\mathbb{Z}$, and in fact every cyclic group is isomorphic to a group of this form. Note that this isomorphism is generally not efficiently computable, which is good because the discrete logarithm problem is easy in $\mathbb{Z}/p\mathbb{Z}$.


Why are these techniques not feasible to crack RSA? For $d = e^{-1} \mod \phi(n)$

$$d\cdot e \operatorname{mod} \phi(n)=1$$
$$d = (e^{-1} \operatorname{mod} \phi(n))$$

With having $e$ and $n$, we can calculate the value of $d$ , the private key for cracking.
Why do people worry about factoring $d$ when this technique is available?
I would like to know some real insight into this.

You are correct in that knowing $\phi(n)$ it is trivial to get the private key back with a simple modular inversion.

However, we are only given $e$ and $n$, and it turns out that computing $\phi(n)$ from $n$ alone is computationally equivalent to finding the factors of $n$. Namely, if you know $\phi(n) = (p-1)(q-1) = (p-1)(n/p - 1)$, you can recover $p$ by solving the quadratic equation $p^2 + (\phi(n) - n - 1)p + n = 0$ for $p$.


Is rainbow table attack applicable to any hash? Typically when rainbow tables are discussed MD5 hash is used as an example. It's not quite clear whether this attack is specific just to MD5 or to a certain subset of hashes or to just any hash function.

Is rainbow table attack applicable to any hash?

Rainbow tables are a size optimization of lookup tables at the cost of time. This is the typical time/memory tradeoff found everywhere in computer science.

However, hash functions themselves are not really susceptible to rainbow table attacks. Rather, it's a specific use of a hash function that may (or may not) be susceptible to rainbow tables. And, even then, rainbow tables are used essentially for finding pre-images of hash functions; e.g., given $H(x)$, find $x$.

For example, suppose you are using a hash function to store the fingerprints of files---just files in general. If you allow sufficiently large files to be stored, say, then this scheme is not going to be very susceptible to rainbow tables: the 'space' of possible inputs to the hash function is just going to be too big to generate a useful rainbow table. You might be able to do it for some subspace, which may or may not be useful, but probably not. The point is that: (1) there are many possible inputs, so many that the table would be huge to be exhaustive, and (2) "all files" is rather general, and while some files are undoubtedly more common than others, this statistical bias is not really well-known.

On the other hand, if you are doing password hashing with the naive "just hash the password", then the space of possible passwords is rather small (for most services), and, most importantly, the distribution of passwords is very non-uniform. A password like 123456 is vastly more common than AvdJv89}{. Hence, you can generate a rainbow table with the top X most common passwords and get significant "coverage" with the table. Given that the goal of password hashing is to keep plaintext passwords out of the hands of attackers for as long as possible, this is quite bad, especially given that the users who are using passwords like 'password123' are probably going to be doing similar things for other services. Thus, with rainbow tables against password hashes, the real idea is to hit the weakest X% of users. That one user with a 48-char password is probably security-conscious enough that it's not worth the effort to break his password, so attackers are mostly interested in users whose passwords are insecure. And, at any rate, that assumes the service allows long passwords; my university allows only up to 24 characters for whatever reason.

This attack is possible really because the preimages we are interested in are (1) few in number and (2) highly biased towards certain preimages. Also, crucially, we already "know" the most common inputs to the hash function. This is why "salting" passwords breaks the rainbow table attack: the random "salt" prevents us from knowing the common inputs, since now there's a salt being sent into the hash function too. If it is a "global" salt and is known to the attacker, then the attacker can generate a rainbow table that uses the 'salt' (a 'pepper' more accurately). But for the case of a real per-user random salt, rainbow tables aren't a possible line of attack.

To answer your question more directly, all of the generic cryptographic hash functions are vulnerable when used in a vulnerable way: MD5, SHA1/2/3, etc. On the other hand, the popular key derivation functions of today (PBKDF2, bcrypt, scrypt) are not vulnerable because they use a salt internally. (Also, for properly-tuned KDFs, the generation of a useful rainbow table would take a very, very, very long time even if a salt weren't used.) The faster the hash function, the faster the rainbow table can be generated, so MD5 is "less secure" against rainbow table attacks in that sense than SHA2.

Keep in mind that the whole point of a rainbow table is to pre-compute values to make finding preimages fast. If you can't predict the preimages you're interested in, then the whole attack is foiled.


AES-ECB known ciphertext/plaintext attack i'm new to crypto and am working on a little exercise to understand the weakness of ECB mode encryption. Here is the scenario.

I have the plain text

I am not tall

and the associated cipher-text generated using an unknown key with AES-ECB.

Is there any way, apart from brute force, I can change generate the ciphertext for the string

I am yes tall

using the information that's available to me?

Knowing the AES-ECB ciphertext for I am not tall does not help you find you the ciphertext for I am yes tall. (Well, it does, but it only rules out one possibility among $2^{128}$ — it can't be the same ciphertext.) ECB has several weaknesses, but not this one. In fact, if you only want to encrypt a single 16-byte message, ECB is fine. The reason ECB is almost never used except by people who don't know better is that encrypting a single message with a forced size is not common.

If the message was longer than 1 block (16 bytes for AES, regardless of the key size), then ECB would start showing its weaknesses. For example, the encryption of I am not tall...I am not tall... is 32 bytes of which the first 16 are identical to the last 16, because the block I am not tall... is encrypted twice. Secure modes vary the way the plaintext is encrypted from block to block; for example, CTR uses the block number, while other modes such as CBC and OFB use some form of “feedback” from one block to the next.

Similarly, if you encrypt more than one message with the same key, ECB will reveal blocks that are common to the two messages. For example, the encryptions of Hello everyone, I am not tall and Hello everyone, I am yes tall start with the same ciphertext block, which is the encryption of Hello everyone, . Secure modes use an initialization vector to make each generated ciphertext depend on something unique: encrypting the same message with the same key but with a different IV produces different results. (CTR's counter isn't exactly an IV, but serves a similar role.)


Testing a steganalysis technique on realistic data I'm developing a new image steganalysis technique, and I'd like to test how effective it is in practice.  How could I do this?  Are there such things as standard "test vectors" for steganalysis?

Are there such things as standard "test vectors" for steganalysis?

Not that I am aware of.

  How could I do this?

Your best bet would be to look for steganographic systems that are out there (either software or a paper describing it). Implement those systems and see how your steganalysis method works. Then you can implement other steganalysis methods from the literature and compare how well yours does vs those.


Expected Linear Complexity of a sequence Let (s) be a sequence of length n. What are the expected linear complexities of (s) and $(s)^{\infty}$ (meaning that the periodic version of s)?

I have no idea of the answer to this question? What does it mean when it say: "expected linear complexity"? Does anyone have any ideas on this issue?

Note that: for sequences which satisfy Golomb's Randomness Postulates, we calculate the "Linear Complexity Profile" of the sequence and  for such sequences it is proved that the Linear Complexity at each step is approximately equal to  n/2. Actually the LC values are in the +(-)5/18  neigbourhood of n/2 line.  But in the above question there is no specification on the randomness of the sequence.

It means (usually) averaged over all sequences of a given length. Rueppel computes this in his book.

It's for an i.i.d. uniform sequence, Proposition 4.6. As $n$ goes to infinity by the law of large numbers this sample mean approaches the actual mean.

This was rigorously proved by Meidl and Niederreiter much later. Behind a paywall but you can see the abstract below:

https://ieeexplore.ieee.org/abstract/document/1042274/

The answer is nearly $n$ for $n$-periodic sequences.


What's the main difference between Pohlig-Hellman and RSA? Both Pohlig-Hellman and RSA perform encryption and decryption by exponentiation modulo some integer ($p$ prime for PH, $n$ composite for RSA). They both use a key $e$ as the exponent to encrypt a message. They both use the inverse element of key $e$ to decrypt. In both, the encryption key $e$ can be a randomly chosen integer coprime with $p-1=\phi(p)$ (for PH) or $\phi(n)$ (for RSA).

So what's the main difference between Pohlig-Hellman and RSA?

Note: The question has been edited for accuracy and more standard notations.

The main difference is that Pohlig-Hellman is a symmetric cypher, while RSA is a public key system.  This is because, with Pohlig-Hellman, anyone who knows the encryption key $e$ can compute the inverse operation (because the 'decryption' key $e^{-1} \bmod p-1$ is easy to compute), while the RSA, someone who knows the encryption key $e$ (but not the factorization of the RSA modulus) cannot compute the decryption operation.


How does sha-2 with fewer rounds work? The wikipedia page about sha-2 states:

  Currently, the best public attacks break preimage resistance for 52 out of 64 rounds of SHA-256 or 57 out of 80 rounds of SHA-512

How exactly is the sha-256 algorithm with fewer rounds defined? I am wondering in particular about the message schedule array $W$, since in round $i$ of the $64$ round sha-256 algorithm, $W[i]$ is accessed. Does 52 round sha-256 simply ignore the elements $53..64$ of $W$?

Does 52 round sha-256 simply ignore the elements $53..64$ of $W$?

Yes; rounds 53-64 don't happens, and we don't actually use elements of $W$.

One alternative way of looking at $W$ is that it's an iterative algorithm to generate the next text-dependent constant for the round function (based on the constants generated for the previous rounds, or the actual message text for the first 16 rounds).  With this formulation, there is now no need to specify a magic number '64'; the number of rounds can be decreased or increased without significantly modifying the block scheduling algorithm


Finding where I am in a linear recurrence relation Suppose I have a linear recurrence relation
$$a(n) = c_1 a(n-1) + \dots + c_k a(n-k) + d,$$
where the constants $c_1,\dots,c_k,d$ are given and the initial values $a(0),\dots,a(k-1)$ are given as well.  Assume that all arithmetic is done over some finite field, say $GF(p)$ where $p$ is a large prime (i.e., everything is done modulo $p$).

Suppose I am given the value of $a(n)$, where $n$ is unknown.  Can I efficiently recover $n$?  Or, more precisely, suppose I am given $b$, with the promise that there exists some $n$ such that $b=a(n)$.  Can I efficiently find some positive integer $n$ such that $b=a(n)$?  (Any integer will do.)

Effectively, if you're given a value from somewhere in the sequence given by this recurrence relation, is there an efficient algorithm to recover the index of that element in the sequence?  By efficient, you can substitute "polynomial time" or "feasible in practice" or something like that.

How does the complexity of this problem relate to the complexity of the discrete log problem?  Are they of equivalent hardness?  Can I use an algorithm for the discrete log problem to solve this problem, or might this problem be harder?

I know the answer will depend upon the particular recurrence chosen: for some it will be easy, for others it will be hard.  Is there any way to characterize or classify for which recurrences this problem is hard?  Maybe some criterion on $c_1,\dots,c_k,d$?

Note that the discrete log problem is a special case of this recurrence relation problem.  In the discrete log problem, we are given $x,y$ where $y=x^n$, and the problem is to find $n$.  This is an instance of the above recurrence relation problem, where the recurrence is $a(n)=x \cdot a(n-1)$, $a(0)=1$.  Given $y$, asking for an index $n$ such that $y=a(n)$ is equivalent to asking for an integer $n$ such that $y=x^n$.  So, the recurrence relation problem I'm asking about is in some sense a generalization of the discrete log problem.  (Also, this implies that there exist recurrences where this problem is as hard as the discrete log, but it does not immediately suggest criteria for when that happens, nor whether there might be any case where this problem is harder than the standard discrete log.)

First of all, your linear recurrence relation is not exactly linear, it is affine. However, in general, it is not difficult to get rid of the constant term $d$.

To do this, define $A(n)=a(n)+t$, and choose $t$ to make sure that the constant term vanishes. This requires $t=(c_1+...+c_k)t+d$, clearly, this can be done unless $c_1+...+c_k=1$.

From now on, I assume that we have no constant term $d$. You want to recover a possible $n$ from a single value $a(n)$. As far as I know, there is no direct relation between this and discrete logarithms.

However, there is a direct relation to the discrete logarithm problem for a simple variant of your question, i.e. given $a(n), a(n-1), ..., a(n-k+1)$ recover $n$.

This variant is a classical question about LFSR (linear feedback shift register). Usually, people consider LFSRs modulo 2, but it is also possible to consider them modulo $p$ and this is precisely what we are doing here.

To the recurrence formula, you can associate a polynomial $P(x)=x^n-(c_n\cdot x^{(n-1)}+...+c_2\cdot x+c_1)$. If you associate to a state $a(1),...,a(n)$ the polynomial $a(1)+a(2)\cdot x+...+a(n)\cdot x^{n-1}$ then updating a state is simply multiplication by $x$ modulo $p$. If this polynomial is irreducible, then finding the correct power of $x$ is simply a discrete logarithm problem in $GF(p^n)$.

When $P(x)$ is not irreducible, you are in fact simultaneously computing the values modulo several irreducible polynomials (and the results are pasted together using the Chinese Remainder Theorem), so you can solve it by computing discrete logarithms in smaller fields.

Coming back to your original question, a equivalent formulation in terms of discrete logarithms is: given $x$ an integer modulo $p$ and an extension field $GF(p^n)$ find an arbitrary element $X$ in $GF(p^n)$ represented by a polynomial whose constant term is $x$, together with a logarithm of $X$.