number of blocks, and size of padding at 64bit A message has 2003 characters, encrypted using a block cipher of 64 bits. What is the size of the padding and the number of blocks?

I tried this, but I'm sure it's not the right thing:

2003 mod 64 = 19, this is the number of bits that needs padding.
2003 / 64 = 31, this is the number of complete blocks, this + 1 = 32 is the total number of blocks.

As written, this exercise is ambiguous, since we don't know how many bits make one character, or even if this number is constant or not.  (For e.g. Unicode text using the UTF-8 encoding, it's not — one character can take up between 1 to 4 bytes, or 8 to 32 bits.)

However, if we assume that one character = one byte = 8 bits, then the message has 2003 × 8 = 16024 bits.  This amounts to 250 (= 16000 / 64) full 64-bit cipher blocks, and 24 bits (= 3 bytes) left over, for a total of 251 blocks (= 251 × 64 = 16064 bits) after padding.

(A perhaps simpler way to calculate this is to note that 64 bits = 8 bytes, and that 2000 is a multiple of 8.  Thus, the message has 2000 / 8 = 250 full blocks and 3 extra bytes, giving a total of 2008 bytes after 5 padding bytes have been appended to round the length up to the next multiple of 8 bytes.)


Replay attack in ECB mode How do replay attacks work in ECB mode?
I found this in Wikipedia:

  "ECB mode can also make protocols without integrity protection even more susceptible to replay attacks, since each block gets decrypted in exactly the same way. For example, the Phantasy Star Online: Blue Burst online video game uses Blowfish in ECB mode. Before the key exchange system was cracked leading to even easier methods, cheaters repeated encrypted "monster killed" message packets, each an encrypted Blowfish block, to illegitimately gain experience points quickly.[citation needed]"

But I want to know how a replay attack really works in ECB mode, and how the other block cipher operation modes (like OFB) avoid it.

A replay attack simply means that an attacker who intercepts a valid message can re-send that message as many times as they want.  If there's nothing in the message that could not be legitimately repeated, then the recipient will have no reason not to accept it as a valid message.

In general, all encryption modes are potentially vulnerable to replay attacks, depending on how they're used.  The usual way to defend against such attacks is to include some kind of unique identifier and/or a timestamp in each message, so that the recipient can detect repeated messages.  The messages should then also be protected against modification using a message authentication code (MAC) or an authenticated encryption mode, so that the attacker cannot simply change the ID or timestamp.

As the claim you quoted from Wikipedia lacks any references that would let me look at the details of that particular attack (or even verify that it really took place), all I can do to answer your question is offer some guesses as to how ECB mode might be more vulnerable to replay attacks, or how other block cipher modes could be made more resistant to them:

First of all, one weakness particular to ECB mode is that you can take two messages, cut them apart at cipher block boundaries and join the halves together again to get a valid message combining parts of the two original messages.  Depending on how the messages are constructed, this might allow an attacker to e.g. glue the contents of an old message to the ID and timestamp from a new message, which obviously defeats their purpose.
Second, other block cipher modes, such as CBC, CFB, OFB and CTR, all require a unique initialization value (IV) or a "nonce" (essentially a unique identifier).  While preventing replay attacks is not the primary reason why these IVs / nonces are required, since they're there and since they need to be unique anyway, they can also be used to detect duplicate messages.

A potentially convenient feature is that, for many (but not all!) modes, even in the absence of a MAC, trying to modify the IV / nonce will turn the entire message into random garbage when it is decrypted.  This is particularly true of the OFB and CTR modes, which are otherwise very vulnerable to ciphertext modification.  (Of course, this is still not a good substitute for a MAC in other respects.)
Finally, in some applications, it might not be necessary to transmit the IV / nonce at all, since it may be inferred from some external information (such as the number of messages or blocks seen before, if messages are transmitted in strict sequence on a supposedly reliable channel).  In some cases, all messages might even be encrypted and transmitted as a single continuous stream, essentially just one long message.

This obviously makes replay attacks on non-ECB modes difficult or impossible, since repeating an old message would just lead to the recipient trying to decrypt it with the wrong IV / nonce.  However, ECB mode still remains vulnerable due to the property described above, namely that, as each block is encrypted independently and in the same way regardless of its position in the stream, an attacker can shuffle (and delete or duplicate) blocks in any manner without affecting their decryption.

Still, I should note that all of these attacks only apply in the absence of authentication.  Even ECB mode, if combined with a MAC and with unique message IDs to detect duplicates, would be secure against replay attacks.  Of course, the same goes for no encryption at all, but just unique message IDs and a MAC, but at least adding ECB mode encryption to the mix wouldn't make things any worse.


Can AES decryption be used as encryption? Definition

E: AES encryption
D: AES decryption
x: plain text
y: encrypted text
k: key

In original AES cipher,

encryption: y = E(x, k)
decryption: x = D(y, k)

Then I define the "reverse AES cipher" as below.

encryption: y = D(x, k)
decryption: x = E(y, k)

Is "reverse AES cipher" safe as original AES?
or, is safe but the strength is not simply comparable with AES?
or, is not safe?

Or, do anyone know any ciphers that can be used as above and are safe and practical as AES?

First, I'll assume we're talking about encrypting/decrypting exactly 128 bits of data, i.e. the block size of AES. Otherwise, you'll need to specify a mode of operation — and if your data's length isn't a multiple of the block size, well, that'll be more difficult to deal with. So, I'll assume we're working with a single block. (If you are using a mode of operation, the below doesn't apply; see the other answer(s) for more details.)

AES models a theoretical construction called a pseudorandom permutation (PRP). Essentially, this means that if we set up a game where we give a polynomial-time-limited adversary access to either (1) an oracle computing a truly-random permutation or (2) an oracle computing the pseudorandom permutation (with a randomly chosen key), the adversary cannot determine which they were given access to with any non-negligible advantage. (They can always guess one or the other, so they have a 50% chance of guessing right; what the PRP security requirement states is that they can't get any non-negligible chance over that 50%.)

There is a stronger notion of a PRP called a strong pseudorandom permutation. In the strong PRP game, the adversary is given access not just to an oracle computing the permutation in question: they're also given access to the inverse of the permutation. In terms of block ciphers, this means that instead of getting access to just an encryption oracle, they would also get access to a decryption oracle.

As far as we know, AES is indeed a strong PRP, so for single blocks, swapping the encryption and decryption functions should be fine. You could then use this in other block cipher modes of operation, for instance.


Does keeping a PGP crypted message private helps? In other words, if I make a PGP crypted message publicly available, do i compromise its security?

In other words which encryption level would guarantee me, say, 20 years of security?

Additionnally, if i keep a bunch of PGP encrypted message with the same private key public, would it helps eventual hackers to decrypt them ?

Of course, if a message is encrypted and on a secure and secret storage it will impossible to compromise its security, because if the message is not available at all to an adversary, how could he attack it?

By the way, if it is correctly encrypted with a key of reasonably length its security is not compromised even if the encrypted message is made available to the adversary. The confidentiality protection is one, the main probably, of the security property of the cryptography and the threat model is exactly this one. Usually in proving encryption schemes the property researcher look for is the semantic security, meaning that even a bit of information cannot be recovered from the ciphertext.

In pratice it depends on your encryption scheme. If the message is encrypted with something that is at the state of the art, well implemented there is no risk and you can sleep well with no worries.

If you want to estimate the time window of security you could check the KeyLength page.

For the same reason keeping several encrypted message togheter does not leak information and does not represent a risk. In security proofs an adversary is supposed to have access to a decryption oracle and he is allowed to ask for a reasonable number of decryptions (but the challenge message) and the encryption is still secure. On the other hand, if your public key is known by the attacker (and it is supposed to be known, as it is public) the attacker is able to encrypt whatever he wants with your key, so he is able to get a bunch of encrypted messages (even better, knwon plaintext and ciphertext).


What is the difference between the adversary and the algorithm? I recently saw a sketch relating to provable security in a book, regarding the amount of time it takes to factor N where N = pq and p,q are primes.

It says that "There is a trivial algorithm which always factors a number in time $\sqrt N$ , so there is an adversary $A$ such that $Adv_b (A, 2^{b/2}) = 1$" b is the amount of bits of $N$.

Here there is a distinction drawn between the adversary and the algorithm. However, if the algorithm can always factor a number in $\sqrt N$ why does it matter, how strong the adversary is?

This statement is just stating that since there exists an algorithm that can factor a number in time sqrt(N), we can use what we know about this algorithm to calculate the probability that the adversary can win an indistinguishability game against a challenger using this encryption scheme.

In other words, the algorithm is used to calculate the advantage of the adversary. Since the algorithm can factor $N$ in time sqrt(N), we must pick big enough primes, so that no probabilistic polynomial time adversary can attack the system.


Hash decrypts key, key decrypts cipher... why? I noticed recently that a couple of pieces of encryption software (TrueCrypt being one of them) don't directly use a hash of the password as the key for the block cipher. Instead, they generate a random key, use that to encrypt the data, then xor the key with the hash of the password and store the result within the encrypted file's header.

I can see this being useful from the perspective of wanting different keys for different files, even though the password is the same, but I can't think of any other reason. Are hashes weak as block cipher keys, or am I missing something here? Are there any additional security considerations to think about with this kind of mechanism? Also, is this mechanism superior to using keyed HMAC hashes, where the file contains the key?

There are several reasons to use a scheme like this:

As several other answers have pointed out, it allows changing the password without re-encrypting the entire file.
Also, it allows re-encrypting the file without changing the password, should this be desired.  In particular, a careful implementation can allow incremental re-encryption, so that the file can be accessed while the re-encryption process is running, and so that the re-encryption process can be safely resumed even if the computer crashes while it's running.
Using an intermediate key also allows multiple passwords to be defined for the same file without having to store all the data twice — just encrypt the same inner key with each password and store them all in the header.

It's also possible to support other authentication methods besides plain passwords; for example, the inner key could be encrypted with the public half of a public/private key pair (RSA, DSA, etc.), with the private key perhaps in turn stored in an encrypted key file and/or on removable media.  You could even have the file accessible both with a password and with a private key file if you like.

(For technical and performance reasons, you do not want to use public-key crypto algorithms to directly encrypt large files, so in practice, whenever you use such keys for file encryption, this is exactly what you do anyway — encrypt the file with a random symmetric key and then encrypt the random key with the public key.)
And yes, it also ensures that two identical files encrypted with the same password won't have the same ciphertext.  Granted, there are other ways of ensuring this, but it's still a useful side effect.


Anonymous Gravatar Problem Gravatar is a service that serves avatars for users based on md5(email_address). The hash is embedded on websites, so it's public.

One of the problems with this solution is that it's easy to track users across websites, since the same e-mail will have the same hash.

I'm wondering if there's a cryptographic solution to that problem? Requirements:

A. It must not be practical to correlate users across websites by the avatar URL alone (hash/identifier for the same e-mail must be different on different sites)

B. The server, given a hash/identifier, can decode it and look user up in a large database in a better-than-linear time.

C. No clock synchronization, no challenge-response protocol (it must be possible to generate identifiers offline). Ideally it shouldn't require pre-shared keys for every website.

The only solution that comes to my mind is something like salt + hash(email_address + salt), which would meet requirements A and C, but not B: salted hash would force the server to re-hash e-mails of all users to find the relevant one.

Encrypt the hash using the public key of the avatar server with ECC. This has a space overhead of 32 bytes (43 Base64 characters). A modern CPU should be able to decrypt about 10000 messages per second per core. If a website uses a fixed key for all the avatars both sides can cache the shared key, so they don't have to pay the cost of the key exchange all the time.

While this solves the "everybody can do an offline search to guess the email matching a hash" problem gravatar suffers from, it doesn't solve all its privacy problems. In particular the avatar service can track users, and the picture data itself allows correlation across sites, even if the hash differs.


Strength of $H(k\|H(m))$ as a MAC algorithm What is the strength of $H(k \| H(m))$ compared to HMAC? Compared to $H(m \| k)$? What is the strength in bits of a given key/output size?

Should be comparable in strength to $H(m||k)$. The weakness is that a collision in the inner hash breaks the MAC. Using strong hashes the strength in bits is $\min(2^{n_O},2^{{n_I}/2})$ where $n_O$ is the output size of the outer hash and $n_I$ the output size of the inner hash.

But since cryptoanalysis usually breaks collision resistance long before it breaks keyed modes like HMAC, it's riskier than the security loss against generic attacks indicates.


Formula of function in MD5 algorithm As i read MD5 have many complex formulas, example:

$k_i := \lfloor \space| \sin(i + 1) \times 2^{32}| \space\rfloor$

My question is why use sin(), how about cos() or tan() or something like that. Does it make any sense when use sin() ? Or just for more complex of formula lead to more secure of algorithm ?

In MD5, the use of formulas with floating point arithmetic is limited to building 64 nothing-up-my-sleeves 32-bit constants. Most implementations use a precomputed table, for startup efficiency and portability.

Changing $\sin$ to $\cos$ would change the constants, but as far as we know would make the algorithm neither weaker nor stronger. That's the nature of nothing-up-my-sleeves constants.

There would be a problem with using $\tan$, because $\tan(11)\approx-225.95$, thus the input of floor would be 40-bit. We would need a floor variant with at-least 40-bit result, keep the low-order 32-bit part of the result, and ensure that $\tan$ is evaluated to at least 40-bit precision in the mantissa for portable values from an implementation to another¹.

MD5 has other arbitrary-looking formulas, operating on 32-bit unsigned integers assimilated to 32-bit vectors. These are optimized for their cryptographic properties, and changing them haphazardly stands high risk of weakening the algorithm (further than it is: its security goal of collision-resistance is not met).

¹ Incidentally: computing the MD5 constants using the built-in floating point arithmetic in the Arduino will fail to yield the correct table due to insufficient (non-conforming) precision of the double type there, and would cause the low-order 8 bits to be severely biased, with possible negative cryptographic consequences. The same effect causes many Arduino code using a GPS to be significantly less accurate than it should be. But I digress.


Does RSA-OEAP have integrity and authenticity properties? RSA-OAEP is IND-CCA2 secure (indistinguishable under an adaptive chosen ciphertext attack). Does it also have the INT-CTXT (integrity of ciphertext) and INT-PTXT (integrity of plaintext) properties?

I don't believe that IND-CCA2 implies these. Are they true for RSA-OAEP though?

INT-CTXT and INT-PTXT are usually on considered for private-key encryption.  For public-key encryption, no correct encryption scheme can satisfy those requirements.  (Proof:  The adversary can run the encryption algorithm on an arbitrary message and submit it as its output.  Since it made no queries to its encryption oracle, this ciphertext violates both INT-CTXT and INT-PTXT security.)


How can a digital signature algorithm incorporate a random data if it is to be authenticated on a separate system I am trying to understand how RSA digital signatures can incorporate any data from a PRNG into the final signature. Does this mean that separate implementations might fail to verify each others signatures if they chose a different method for coming up with random padding based on the input or a hash of the input?

Is this something that is different between RSASSA-PKCS1-v1_5 and RSASSA-PSS?

RSASSA-PKCS1-v1_5 does not use random padding, the scheme is deterministic.

  RSASSA-PSS is different from other RSA-based signature schemes in
     that it is probabilistic rather than deterministic, incorporating a
     randomly generated salt value.

The signature is verified using a hash over the message hash and the salt. So the verifier does not need to know how the random is generated, it will just verify the hash over it. Check steps 9 to 14 of the PSS signature verification of RFC 3447 paragraph 9.1.2.


How does this solution guarantee authentication of B and privacy? The exercise is:
What could be changed on the second message " Kya(Kxb(Ra,Ks)) "  to guarantee B's authenthicity and also privacy?

My teacher's solution was "add a destination" , so it would be something like this
Kya(Kxb(Ra,Ks,A)).

If we have a man in the middle, Trudy pretending to be B, couldn't she just check the contents of the message and send them to A? (I'm not sure if it works that way), but this is my understanding, something like this:

1- A -> A, Kxa(Ra, Ts) ->T -> A, Kxt(Ra, Ts) ->B

2- A <- Kya(Kxb(Ra, Ks, A)) <- T <- Kyt(Kxb(Ra, Ks, A)) <- B

I'm not quite sure how does the "Destination" field solve anything.

Also as indicated in this answer to a related question made by the user Maarten Bodewes, here's the meaning of those operations:

A is the identity of A, which can be used to select the right public key of A;
Kxa() is a signing operation (with message recovery) that signs the random Ra and a tag Ts which is used as proof;
Kya() is an encryption operation with the public key A, so that the session key Ks is kept confidential;
Kxb() is a signing operation (with message recovery) that signs the random Ra together with session key Ks;

Let's assume that T does send A,Kxt(Ra,Ts) to B as you have indicated. In that case upon reception and validating the signature, B would immediately be able to tell that the signature does not belong to A (and should thus not continue the exchange).

To try to take advantage of the exchange, T would have to alter the message from A so that it still looks legitimate (i.e. where the attached originator matches the signature), while substituting it's own identity to A's when interacting with B (so that B would reply with an encrypted message for T instead of for the original A; B has otherwise no reason to encrypt using Kyt as you've indicated in step 2). This could be done by changing the message from A,Kxa(Ra,Ts) to "T,Kxt(Ra,Ts) as T intercepts the message. At that point one of two things can happen:

B already knew A's identity, and would immediately be able to tell that T,Kxt(Ra,Ts) is not from A.
B does not have prior knowledge of A's identity. He then validates the message signature Kxt(Ra,Ts) which look like a valid signature for the attached identity T. Since it looks ok, he proceeds to generate Kyt(Kxb(Ra, Ks,T)) which T could decrypt to obtain the much needed Ks. However, since T cannot forge B's signature to generate Kxb(Ra,Ks,A), T can either send Kya(Kxb(Ra,Ks,T)) (a message properly signed by B which reveals T's identity to A) or Kya(Kxt(Ra,Ks,A)) (a message which attempts to hide T identity, but which is visibly not signed by B) to A. In either case, A knows that the channel is compromised and should not continue the exchange.


3-round DES: what bit do we find? (Regarding matsui's Paper on Linear Cryptanalysis of DES) In Matsui's paper, Section 5 ‘Linear Approximation of DES Cipher’, Matsui gives two similar equations: Eq. (6) for the first round and Eq. (7) for the third round.
The two equations give an approximation of bit $K_1[22]$ and bit $K_3[22]$. Then he derives in Eq. (8) from Eqs. (6) and (7) an approximation of $K_1[22] \oplus K_3[22].$

From what I understand, the 3-round DES linear approximation is supposed to give an approximation of only one bit of the key, but here I see two bits from the partial key.

Which bit of the actual key does this approximation refer to?

The equation in (8) is obtained by summing (6) and (7), and is an approximation for the bit
$$
K_1[22]\oplus K_3[22].
$$
The sum of two key bits is still a bit.


Does SipHash have 64 bit (second) preimage security? I was not able to find an explicit statement about the first and second preimage security of SipHash-2-4 or SipHash-4-8 anywhere.

I think it should be 64 bits, but I'd feel safer if somebody who has more experience with such hash functions could confirm this?

PS: I am aware that 64 bits can be broken, but I only need short term protection and I want to keep my packets small.

SipHash is a MAC (aka Pseudo Random Function Family) with 64-bit output and 128-bit key, rather than a hash (aka random public member of a Pseudo Random Function Family). It is explicitly designed to be used with a secret random key. Quoting Jean-Philippe Aumasson and Daniel J. Bernstein's SipHash: a fast short-input PRF (in proceedings of Indocrypt 2012):

  the standard PRF and MAC security goals allow the attacker access to the output of SipHash on messages chosen adaptively by the attacker. However, they do not allow access to any "leaked" information such as bits of the key or the internal state. They also do not allow "related keys", "known keys", "chosen keys", etc.

Thus you are without endorsement of the creators if using SipHash as a hash function and expecting 64-bit second preimage resistance when the key has gone public (as you would legitimately for a 64-bit hash function).

This does not answer the question of if preimage resistance of that SipHash-turned-hash can be broken much better than by brute force (expected $2^{64}$ evaluations of SipHash, which is not much); I simply do not know, and find it nontrivial to make an opinion other than: uncertain.


Why is it that in DSA, the order of the subgroup, $q$, is chosen such that it divides $p - 1$? Consider the DSA key generation:

A large prime $p$ is chosen;
A smaller modulus $q$ is chosen such that $p - 1$ is a multiple of $q$;
A generator $g$ s.t. $\operatorname{ord}_p(g) = q$ is chosen.

My question is -- why do we require that $p - 1$ be a multiple of $q$?  Is there any underlying mathematics I'm missing?  Thanks.

As was noted in the comments the reason for $q$ having to divide $p-1$ is Lagrange's theorem:

  Lagrange's theorem [...], states that
  for any finite group $G$, the order (number of elements) of every
  subgroup $H$ of $G$ divides the order of $G$.

In the case of DSA we are working in subgroups of $\mathbb F_p$ (which has order $p-1$). By Lagrange's theorem every subgroup has to have an order $q$ such that $q$ divides $p-1$.


Diffie-Hellman coloured abstraction Confused with color abstraction in this video.

Bob has:

public color;
mixture from Alice;
can produce random color;

Eve has:

public color;
mixture from Alice;
can produce random color (why not?);

Bob can produce same shared color as Alice did, Eve cannot. Does it make sense?

Bob has his private color and mixture from Alice. When he mixes them up he has the same color as Alice when she mixes up mixture from Bob and her private color.

Eve has only two mixtures but no private color, so she can't produce the same color as Alice and Bob.

Eve here can only see colors Alice and Bob exchang but can't change them (Eve is for eavesdropper), if she can change them (intercept mixture from Bob and send her mixture instead) she should be called Mallory (from man in the middle). In this case we have to assume that Alice knows Bob's mixture - he showed it to her earlier in real life or something - and she won't be tricked by fake mixture Mallory sent her.


What's the difference between block ciphers and symmetric-key encryption? Both block ciphers and symmetric-key encryption use a secret key to transform plaintext into ciphertext, and do so in a reversible manner. Are they the same? Or does symmetric-key encryption also includes things other than block ciphers?

Symmetric-key scheme just means use a key to encrypt and decrypt the same message.

Block ciphers just means encrypt your data in many small bits blocks (which can vary in size with padding randomized technique).


Why 64 bits output hash function is insecure I know this is a insecure design to 64 bits output size hash function. Is there any report or literature illustrate this condition. I want to do some relevant reading about it.

The answer is easy if you know about the current computing power around the world

Bitcoin miners in 2020/1/17 they reached 126.1314 Exahashes per second, that makes

$2^{67}$ SHA256 double hashes in a second, and
$2^{92}$ SHA256 double hashes in a year.

With 64 bit output from the hash function, you will have

64-bit pre-image resistance, broken less than a second.
64-bit second pre-image resistance, broken when you click the enter.
32-bit collision resistance due to the birthday attack that has a 50% chance of collision. You will find a collision while your finger on the enter key.

In today's standard, the recommended has size is at least 224 bit by SHA256-224 if you consider all available NIST hash families after the SHA-1 which has 160-bit output.

There are also single super computers like Summit, that can reach ≈$2^{63}$ SHA-1 hashes around one hour, ≈$2^{72}$ hashes in one year.
1


How long would it take for a sha256 digest loop to reach the original hash or start cycling? If I started with a sha256 hash such as

3f46fdad8e5d6e04e0612d262b3c03649f4224e04d209295ef7de7dc3ffd78a7

and rehashed it continuously (without salting):

i) What is the shortest time it would take before it started cycling in a loop or back onto the same value if at all?

ii) If it did cycle back on itself, could we assume that it had been cracked?

iii) How long would this take using modern GPU cracking techniques?

iv) If all the intermediary hashes were recorded in some kind of rainbow tables - presumably all the hashes within that cycle would be compromised?

v) What is to stop someone computing these cycles and offering cracks to sha256 hashes - likewise for other hashing protocols...

For Extra marks - What is the probability this question would be asked in this forum 60 billion years ago?

What is the shortest time it would take before it started cycling in a loop or back onto the same value if at all?

Well, strictly speaking, it's possible (albeit unlikely) that the first hash output would happen to be the initial value, and so the "shortest time possible" would be one hash.

However, lets do some analysis to see when it's likely to happen.

Let us assume that SHA-256 acts as a Random Oracle (it has no known ways it doesn't act like a Random Oracle on fixed length inputs).  Then, for a hash chain of length $n$, you have $n+1$ outputs, and hence $(n+1)(n+2)/2 \approx n^2/2$ pairs of outputs, and for each pair, we have a probability of $2^{-256}$ of them happening to collide (actually, this isn't exactly correct, but it's close); hence, if $n \ll 2^{128}$, we have a probability of circa $2^{-257}n^2$ of there being a collision (again, this isn't precisely correct, because the probabilities are not independent, but it's close).

So, to get a probability of $2^{-30}$ of falling into a loop, we would need a chain of length $n$ where $2^{-30} \ge 2^{-257}n^2$ or $n \ge 2^{113.5}$ long.  If your hardware can compute $2^{30}$ SHA-256 hashes per second (real hardware can't go this fast), then it'll take around 30 million times the current estimate of the age of the universe.

  How long would this take using modern GPU cracking techniques?

Well, a quick Google search finds the fastest GPU doing about 3 billion SHA256 hashes per second.  Let us assume that you have a GPU farm with a million of these GPUs, and let us also ignore the issue that computing a hash chain is an iterative process (and GPUs want to compute things in parallel).  Then, using the above estimates, to get to a 1-in-a-billion probability of finding a collision, we get the expected time down to about 10 times the age of the universe.

  For Extra marks - What is the probability this question would be asked in this forum 60 billion years ago?

Probability is 0; this forum didn't exist 60 billion years ago :-)


Camellia or AES - which should I use? Imagine I am a software developer.  I want a block cipher, and I have the choice of using AES or Camellia.  Which should I use?  Which makes more sense from a technical perspective, and why?  I need to select the preference order for TLS ciphersuites: should I put the AES ciphersuites above or below the ciphersuites?

For example, Firefox's SSL/TLS libraries currently list Camellia ciphersuites as preferred over AES ciphersuites.  Is that the right choice?  Should others follow Firefox's lead, or should they list AES ciphersuites as preferred over Camellia?

(See also Why does nobody use (or break) the Camellia Cipher? and Why is CAMELLIA suddenly so widely used?, which are related but not identical.)

From a technical side, there are three general scenarios that should be handled differently:

Scenario 1: You control the configuration of the server your client software will connect to, and expect to retain that control for the life time of your client software. In such case, you only have to (and probably should) enable a single cipher suite, both client side and server side. Given a choice between several cipher suites that all meet your minimum requirements, and presuming there is at least one AES cipher suite in this list, choose that one (for the reasons stated here).

That said, you obviously would have to enable more than one cipher suite if you are bound by a security requirement to have a fall back option, e.g. in case the cipher suite gets broken and your software upgrade mechanism is more likely to fail, than your ability to reconfigure the server. This is however the only technical reason to enable more than one cipher suite in this scenario.

If you know that the server implementation respects the cipher suite preference of the client, it might matter how the client orders the cipher suites. Generally, though, the TLS standard does not specify how the server should pick the cipher suite, so this would be implementation specific and a better question for stackoverflow.

Scenario 2: You do not control the configuration of the server, e.g. because your client software might connect to multiple servers, but you do know the configuration of a required minimum of the servers. If there is more than one cipher suite in the intersection of the cipher suites supported by these servers, and that set contains at least one AES cipher suite, the situation is not much different from scenario 1, except possibly that you might be more likely to be required to include a fall back option in this scenario.

Scenario 3: You do not control the configuration of the server, and your security requirements are different for different servers and different users. The intersection of these requirements is the empty set. In this scenario you are basically out of luck. Your best option might be to make the client cipher suites user configurable for someone with administrator privileges, but that would fall outside of the scope of cryptography and be a better question for IT security.


Are there example certificates available for test purposes? Are there example certificates (PEM format) for testing available somewhere ?
For test purposes I would need a certificate signed with SHAS256/ECDSA P-256, together with a complete chain to test verification.

I used the XCA tool. It allows creation of certificates.


LFSR dynamic mutation In normal LFSR, the state is a function of the initial seed, taps positions and time, nothing else. I've seen a modification of LFSR that works like this:

TAPS = const
MASK = (1<<L)-1 #L=bitlength of state

def parity(x):
    return (number of ones in x)&1

def tick(state):
    b = parity(state & TAPS)
    return (state<<1 | b) & MASK

while True:
    i = 0
    k = [...] #elements smaller than bitlength of state
    while True:
        state = state ^ (1<<k[i%C]) #C<=length(k)
        state = tick(state)
        i += 1

I can't find any mention of that variant in the literature. Does it have a name, or is it completely custom?

I have never met this, but it can still be analyzed in the framework of Linear Feedback Shift Registers, and is unsafe as a key stream generator.

I'll assume that $2^{\mathtt L-1}\le \mathtt{TAPS}<2^\mathtt L$. The operation state = tick(state) then is the normal operation for a Fibonacci LFSR with the binary polynomial $Q(x)$ of degree $\mathtt L$ defined by the bits set in the integer $2\cdot\mathtt{TAPS}+1$.

The addition of state = state ^ (1<<k[i%C]) turns that into a different beast, in particular the state now includes $\mathtt i\pmod{\mathtt C}$, sort of extending the state from $\mathtt L$ bits to $\mathtt L+\log_2\mathtt C$ bits.

However, the transformation corresponding to $\mathtt C$ steps leaves $\mathtt i\bmod \mathtt C$ unchanged, and is a linear transformation of $\mathtt{state}$. For moderate $\mathtt C\cdot\mathtt L$, blindly applying a good tool based on the Berlekamp–Massey algorithm on known output will allow prediction of the rest, without any description of the system.

Update: At step $\mathtt i$, $\mathtt{state_i}$ has bits sets as per the coefficients of the remainder of the division by polynomial some appropriate reduction using $Q(x)$ (defined above) of the sum of two polynomials:

$x^\mathtt i\cdot S(x)$ where $S(x)$ corresponds to bits set in $\mathtt{state_0}$, as would be the case for a normal LFSR;
$\sum_{\mathtt j=0}^{\mathtt i-1}x^{\mathtt{k[}\mathtt j\bmod\mathtt{C]}+\mathtt i-1-\mathtt j}$, corresponding to the effect of state = state ^ (1<<k[i%C]).

To answer an additional question: in general, $\mathtt{k[]}$ can not be reconstructed from $(\mathtt{TAPS}, \mathtt L, \mathtt C, \mathtt{state_0})$ and a single $(\mathtt i, \mathtt{state_i})$. When $\mathtt C>\mathtt L$ an amount-of-information argument shows that we do not have enough input. And even for $\mathtt C\le \mathtt L$ there can often be several solutions.


How is R-LWE related to lattice cryptography and homomorphic encryption? Can someone tie everything together for me? I'm interested in H.E and I have some background in AES, DES, RSA and the like. While reading around I stumbled on Shai Halevi's course on lattice cryptography as well as Vaikuntanathan's course.
Looking around I found Fully Homomorphic Encryption from Ring-LWEand Security for Key Dependent Messages which didn't really help me solidify the concepts I'm learning.
I "know" that lattice cryptography revolves around lattices and finding shortest vectors which is thought to be(?) NP-hard. I also found Homomorphic Encryption, LWE, and Practical Applications but it seems the asker there is ahead of me in terms of understanding how everything ties together

While I still think it would be good for you to ask more specific questions, the following might be useful in clearing up your understanding of the underlying hard problems on lattices. I do not see a way to discuss homomorphic encryption as well without essentially writing some (informal) lecture notes, so won't in this answer.
The LWE Problem:
The central hard problem for building constructions in lattice-based cryptography is the Learning With Errors problem.
There is a search and decisional form. The decisional form is to distinguish:
$$(A, As + e)\stackrel{?}{\approx}_c(A, u)$$
Here:

$A \gets\mathbb{Z}_q^{m\times n}$ is a uniformly random matrix
$s\gets \mathbb{Z}_q^n$ is a uniformly random vector
$e\gets \chi^m$ is a random "concentrated" value (meaning $\lVert e\rVert_\infty$ is "small").

The search problem is to recover $s$, given $(A, As + e)$.
This problem has a natural coding-theoretic [1] interpretation --- we can view $A$ as being the "generator matrix" of a random code, and $As + e$ being an encoding of $s$ under the aforementioned code that is sent through some "noisy" channel.
In this setting, the problem of recovering $s$ is equivalent to the problem of decoding a random linear code, which is thought to be hard. Note that this is a problem we would want to do in practice --- random linear codes tend to achieve optimal parameters (up to constant factors), so coding theorists would be very happy if we could decode them.
Average-case Hardness:
Before discussing lattices more, I'll quickly discuss average-case hardness (as this is quite relevant to lattice-based cryptography). There are roughly two settings where one can discuss the complexity of some problem:

In a "worst-case" setting. I.e., given any input instance, how long does it take you to solve the problem?
In an "average-case" settting. I.e., given an input instance drawn at random from a particular distribution, how long does it take you to solve the problem?

Concepts such as NP-hardness discuss the former, but they are not particularly useful for cryptography.
This is because one can have problems that are worst-case hard, but "most" instances of the problem are easy.
If one chose an "easy" instance of the problem during key generation in some cryptographic construction, it could lead to the scheme breaking, despite the problem being worst-case hard.
This means that cryptographic constructions have to pin down some distribution such that the underlying problem is thought to be average-case hard.
This can be more involved than you may think. If you think the underlying problem for RSA being "Factoring" vaguely, then one quickly runs into the unfortunate fact that random numbers are not too difficult to factor (for example, they are divisible by 2 with probability $1/2$ --- depending on how you define the factoring problem this may already suffice to "break" it). One can think about the problem of factoring semi-primes as being the general factoring problem where one specifies a plausible average-case hard distribution (that of semi-primes). This distribution is only plausibly hard though, and there are a number of non-trivial attacks depending on how a particular RSA instance is generated (for example, Pollard's $p-1$ algorithm). This is all to say that you can find some distribution over RSA instances which is likely average-case hard, but it is a more involved process than "just picking things randomly", and that the existence of non-trivial attacks even against the factoring of semi-primes means that we are really left with heuristic hardness of factoring in the end (although this has been fairly resilient over the years).
Lattice-based cryptography differs from this in a significant way due to the existence of worst-case to average-case reductions [2]. This essentially means that there exists some worst-case problem called SIVP (a slight generalization of the shortest vector problem you allude to) such that one can roughly [3] prove something of the form:

If SIVP is worst-case hard, then LWE is average-case hard

This is to say that lattice-based cryptography has a formal proof that the LWE distribution has a certain amount of average-case hardness, provided that a certain natural problem is worst-case hard.
The Ring Setting:
In the above I have only talked about LWE. The "Ring" setting (so working with RLWE rather than LWE) can be viewed as not choosing $A$ to be uniformly random, but instead uniformly random over some "structured subset of all matrices". This is not the most natural way to discuss things from a mathematical perspective, but may be useful initially.
This structured subset admits a compact representation, and more efficient operations generically.
This is to say that RLWE is mostly a way to improve efficiency, which while quite important in practice is not necessary to get the broad picture of lattice-based cryptography.

[1] There are some nuances here, the linear code should not be viewed as being a code in the binary symmetric channel (i.e. a "code with respect to the Hamming norm"), but instead in the additive white gaussian noise channel (say if you take $\chi$ to be discrete Gaussian, which is common).
[2] Note that there are other cryptographic problems with randomized "self-reductions" (for example it is know that if the discrete-log problem is worst-case hard, then it is average-case hard as well). The reductions in lattice cryptography are notable for being to an independently-studied (at least in the non-ring setting) worst-case problem.
[3] There are many caveats one must state here, but the largest one is that one does not work with SIVP in lattice-based cryptography, but instead an approximate version of it. It is known that this approximation problem is in $\text{NP}\cap\text{coNP}$, i.e. is not NP hard unless the polynomial hierarchy completely collapses, which is thought to be unlikely. Other caveats are mostly that there are many ancillary parameters that must satisfy certain inequalities. This is important in practice, but can ignored when just trying to get intuition.


RSA algorithm's license free or paid? I checked RSA's patent application, which was registered in 1983. As patents don't last more than 20 years, it seems to me it should be free. But my friend said to use RSA I have to buy a license from MIT. Is it true ?

You are correct, anyone can use it without asking for permission or paying anybody.  The RSA patent US 4,405,829 expired in 2000, and the RSA algorithm was never patented anywhere else (because the rest of the world won't allow you to patent something that has already been published; the US gives you a year).


"Practical" operations supported by functional encryption? I'm curious about what operations have been developed into functional encryption schemes.

What I mean by that is: what operations can be performed over encrypted ciphertexts? Obviously homomorphic encryption allows for $+$ and $*$. Deterministic encryption allows for equality comparison ($==$). Order-preserving encryption allows for $<$. What other schemes exist that allow for other operations?

I'm primarily concerned with schemes that are implementable so that their running time is fast enough to be practical. I am aware of the recent result for general case functional encryption, but it is far from being useful because it is so slow.

I think you are confusing functional encryption and homomorphic encryption.

In a functional encryption scheme, using a secret key for some function $f$ on a ciphertext $c$ which is an encryption of $m$ allows you to get $f(m)$ in clear.
In an homomorphic encryption scheme, you can run some operation on ciphertexts, and get an encryption of the result, for example in multiplicatively homomorphic encryption, $c_1c_2$ encrypts $m_1m_2$ if $c_i$ encrypted $m_i$.

If you want some answers about homomorphic encryption, there exists homomorphic encryption for addition and multiplication, and somewhat fully homomorphic encryption, which supports both of these operation, but there is a noise growing with each operation that reduces the probability of decryption each time an operation is run -this is only a small problem because given the number of operation you want to make, you can set the parameters of your scheme according to that.

If you want answers about functional encryption, recents works follow two paths:

Ineficient, theoretical functional encryption for all circuits. Which is really interesting for science but is really not practical for the moment.
Predicate encryption, which is all-or-nothing decryption based on an attribute given in the ciphertext and an attribute of each secret key. There should be practical particular predicate encryption such as Attribute Based Encryption or Identity Based Encryption.

If you want practical scheme that give partial information on the message with depending on the key you have, I don't know of many, but I have a paper that will be presented at PKC15 about Simple Functional Encryption Scheme for Inner Product, this scheme enables you to decrypt $<x.y>$ given a $ct_x$ and $sk_y$.


Comparison on Gentry's Fully homomorphic Encryption? This topic is very new to me. Is it possible to do comparison on the encrypted data(data is encrypted using Gentry's FHE)? If so, how can it be done?

Yes, it is possible. I remember at least of the article Low Depth Circuits for Efficient Homomorphic Sorting in which comparisons are discussed.

Encrypt you $\ell$-bit integers $a$ and $b$ bit by bit generating to $\ell$-dimensional vectors $(a_1, ..., a_\ell)$ and ($b_1, ..., b_\ell)$.

Than, to test homomorphically whether $a \le b$, do

$$C_{LT} =  \sum_{k=1}^{\ell} (f(a_k, b_k) \cdot \prod_{k<t<\ell}g(a_t, b_t))  \mod 2$$

Where $f(a_k, b_k) = b_k \cdot (a_k + 1) \mod 2$ is "less than" for bits and $g(a_t, b_t) = b_t + a_t + 1 \mod 2$ is a "equal to" for bits.

Notice that the product from $k$ to $\ell$ can be performed in depth $\log(\ell - k)$ instead of in depth $\ell - k$.

You will probably find other results about homomorphically comparison by searching for articles that cite the one I put here.


Is it possible to affect the output of HMAC w/ SHA-512 by providing it with a custom message? Consider an HMAC algorithm that uses SHA-512 with an unknown private key. Is it possible to affect its output, either partially or totally, by providing it with carefully crafted messages?

For the purposes of this question, consider that the application "updates" its state using our hand-crafted message plus a string that changes on each request which is also known to us. Additionally, consider that we are able to ask the service to sign for us an arbitrary number of messages.

Consider an HMAC algorithm that uses SHA512 with an unknown private key. Is it possible to affect its output, either partially or totally, by providing it with carefully crafted messages?

Sure, however you will get totally unrelated HMAC output even if you change (or add or remove) even a single bit from the HMAC input. So each bit flips with a 50% certainty. Creating "crafted messages" doesn't have any effect on this property.

If you are looking for a specific output then you won't be able to get it, assuming that at least, say 64, bits of HMAC output is kept (if that's the case you might try and brute force). Similarly for other properties, the outcome of HMAC is totally dependent on chance if you don't know the key and /or input message.


Security strength of RSA in relation with the modulus size NIST SP 800-57 §5.6.1 p.62–64 specifies a correspondence between RSA modulus size $n$ and expected security strength $s$ in bits:

Strength  RSA modulus size
  80        1024
 112        2048
 128        3072
 192        7680
 256       15360

This works out to approximately $s \approx 4 n^{0.43}$ (but I have no idea whether my extrapolation means anything; strengths up to 112 are indexed on DES while strengths 128 and above are indexed on AES, i.e. the strength is the difficulty of brute-forcing the corresponding symmetric algorithm with the specified key size).

What are these numbers based on? Do they come from the expected complexity of the best known factorization methods? Or are they extrapolation from the amount of computation in specific factorization efforts such as for RSA-768 (which “required more than $10^{20}$ operations”)?

(I'm asking for more precise information than Difficulty of breaking RSA for a given key size. How big an RSA key is considered secure today? has a nice history of RSA factorizations, but doesn't answer my question — is that what the strength estimates are based on?)

Those appear to be based on the complexity of the General Number Field Sieve, one of the fastest (if not the fastest) classical factoring algorithms. I confirmed this in Mathematica.

Here is the complexity for the GNFS (source):

$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right)$$

where $n$ is a number to factor. Evaluating the above expression at $2^b$ is a rough approximation of the the time needed to factor a $b$-bit integer. Here's a table showing the bit-length of the evaluation at $2^{1024},2^{2048},\dots$:

Strength  RSA modulus size   Complexity bit-length
  80        1024               86.76611925028119
 112        2048              116.8838132958159
 128        3072              138.7362808527251
 192        7680              203.01873594417665
 256       15360              269.38477262128384

I generated these numbers with the following Mathematica code:

({#, N@Log2@gnfsComplexity[2^#]} &) /@ {1024, 2048, 3072, 7680, 15360}

where gnfsComplexity is defined as:

gnfsComplexity[n_] := Exp[(64/9 * Log[n])^(1/3) * (Log[Log[n]])^(2/3)]

which is not the prettiest thing I've ever written, but it seems accurate. (For those unfamiliar with Mathematica, the second code snippet defines a function that's a transliteration of the above GNFS complexity for a number $n$. The first code snippet evaluates that complexity at $n=2^{1024}, 2^{2048}$, etc., takes the logarithm base 2, and converts it to a numerical approximation — a decimal number — instead of an exact result like a fraction.)

As for the reasoning behind the larger key sizes for RSA, the explanation's not too difficult. If you look at the document in the question, you will notice that the "bits of security" for block ciphers correlate almost perfectly with the size (in bits) of the keys for that block cipher (with rare exceptions). This is because our best attack on a secure block cipher essentially is a brute-force search for the key, which on average takes $2^{n-1}$ time where $n$ is the bit-length of the key.

However, for RSA, our best line of attack is not to execute a brute-force search for the key; instead, we "simply" factor the (public) modulus, so the security of the scheme revolves around the efficiency of factoring. The GNFS has a sub-exponential but still super-polynomial time complexity, and one can use this time complexity to roughly approximate the security offered by the scheme. I believe that's what the NIST is doing here.


Explain the fast Walsh–Hadamard transform in simple steps or pseudocode I've read that the fast Walsh–Hadamard transform is a way to efficiently calculate the linearity/non-linearity of an S-box. Can I get a description of it in simple steps or pseudocode that is restricted to simpler notation and terminology?

The fast Walsh-Hadamard transform algorithm generally applies to Hadamard matrices $H_n$ which are of dimension $2^n\times 2^n, n\geq 1$. Using row and column transpositions, $H_n$ can be arranged so that it is of the form
$$H_n = \left[\begin{matrix}H_{n-1}& H_{n-1}\\H_{n-1}& -H_{n-1}\end{matrix}\right].$$ As a special case, note that
$$H_1 = \left[\begin{matrix}+1& +1\\+1& -1\end{matrix}\right].$$

Now, the Hadamard transform of the (row) vector $\mathbf x$ of length $2^n$
is the row vector $\mathbf xH$ where, if we partition $\mathbf x$ as the
concatenation of $2^{n-1}$-vectors $\mathbf x_L$ and $\mathbf x_R$
$\bigr($that is, $\mathbf x = \big[\mathbf x_L, \mathbf x_R\big]\bigr)$, then we can write
$$\mathbf xH = \big[\mathbf x_L, \mathbf x_R\big]\left[\begin{matrix}H_{n-1}& H_{n-1}\\H_{n-1}& -H_{n-1}\end{matrix}\right]
= \big[\mathbf x_LH_{n-1}+\mathbf x_RH_{n-1}, \mathbf x_LH_{n-1} - \mathbf x_RH_{n-1}\big].$$
This suggests that if we have already computed $\mathbf x_LH_{n-1}$ and $\mathbf x_RH_{n-1}$, we can compute $\mathbf xH$ in $2^n$ more additions/subtractions. So, we can proceed recursively, partitioning $\mathbf x_L$ into $\big[\mathbf x_{LL}, \mathbf x_{LR}\big]$ and
$\mathbf x_R$ into $\big[\mathbf x_{RL}, \mathbf x_{RR}\big]$, and
repeat the above calculations with shorter vectors,....

Pseudocode
would be something like

recursive function FHT$(\mathbf x)$
begin
partition $\mathbf x$ into two equal-length parts $\mathbf x_L$ and $\mathbf x_R$
$\mathbf y_L$ = FHT$(\mathbf x_L)$; $\mathbf y_R$ = FHT$(\mathbf x_R)$
return $\big[\mathbf y_L+\mathbf y_R,\mathbf y_L-\mathbf y_R\big]$.
end

The total number of additions/subtractions is $n2^n$; there are no multiplications needed


Explanation of CAVP format for NIST Test Vectors for SHA-2 and 3 I want to run the SHA2 and SHA3 NIST algorithm test vectors provided in the zip files at the bottom of this page:
http://csrc.nist.gov/groups/STM/cavp/secure-hashing.html#sha-2

I don't quite understand how the test vectors are encoded. For example, if I run the SHA2-256 algorithm on an empty string as so:

import hashlib
sha2_256_test_str = b""
sha2_standard = hashlib.sha256(sha2_256_test_str).hexdigest()

I obtain the hash:

e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

Which is correct. However, if I look at the first test vector in the NIST zip file it says that:

#  CAVS 11.0
#  "SHA-256 ShortMsg" information
#  SHA-256 tests are configured for BYTE oriented implementations
#  Generated on Tue Mar 15 08:23:38 2011

[L = 32]

Len = 0
Msg = 00
MD = e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

This would seem to indicate to me that for a message of "00", I should receive the hash above. However, this is the hash I obtain for an empty string. So for instance, the way that I interpret to run this test vector in Python is:

import hashlib
sha2_256_test_str = b"00"
sha2_standard = hashlib.sha256(sha2_256_test_str).hexdigest()

But this gives the hash

f1534392279bddbf9d43dde8701cb5be14b82f76ec6607bf8d6ad557f60f304e

What key point am I missing here? How would I be able to convert the messages in the NIST zip files to a message for my Python script?

All of your questions are answered in the Validation System documents that are linked to by the algorithm test pages.  In this case, look at http://csrc.nist.gov/groups/STM/cavp/documents/shs/SHAVS.pdf

For this case, the message length is expressed in bits not bytes. The fact that the message is also encoded as value of 00 should be ignored in the test vectors smaller than one byte; this just adds confusion to the reader.

Len = The length of a message in bits


Can compressed data be made to look like random data? I saw the question "Decryption honeypots" and realized that if the message was compressed before being encrypted, then checking compressibility would not help you identify the decoded message.

So if the message is compressed by a known method is there a fast way to determine if it is a compressed message (right key) or random data (wrong key), without attempting the decompression method every time?

Edit: I was thinking about a scenario with large (1 gigabyte uncompressed), relatively verbose files like XML which can have a compression ratio of 8:1 An Analysis of XML Compression Efficiency, using a compression algorithm with an output that is nearly uniform. Also with padding on the compressed message to avoid attacks like CRIME as mentioned in the answer below (it seems hilarious to zip something smaller then pad it back to the same size, but this is to hopefully make it harder to decrypt).

TL;DR: yes it can look more random than the plaintext message itself, but it won't help you against crypt-analysis and in the worst case it may introduce vulnerabilities.

I guess the most boring but most effective way is simply to look for meta data within the compressed message. E.g. the precise compression mechanism and compression level may well be within the decrypted message.

Generally you assume that the protocol is known (Kerckhoff's principle). Note that finding out the compression used is usually not hard, and you only have to do so for a single message.

Once you know the compression method checking the correctness of decryption is as easy if not easier; you can always first decompress before checking the correctness of the decrypted message.

Decompressing a message may well be faster than decrypting it. Performing the compression is usually slower as it needs to look for patterns. Compression will only add a single additional step to the crypt-analyst; it's not something you do to make your protocol more secure against brute force attacks. Basically you could compare it to adding a single bit to the security level at most.

An attacker may always use compression on a (set of possible) known plaintext and compare against that, resulting in a meet-in-the middle attack.

Compression in cryptography is a very dangerous thing. Some plaintext compress better than others and smaller plaintext generally lead to smaller ciphertext. So even if the plaintext is the same size, compression may confer details about the plaintext to an attacker. Take for instance a look at the CRIME attack against TLS for an example of this.

Compressed or inflated data usually does not look like random data, and it is a very dangerous to see it as a security feature. It is much more likely to add insecurity than security when trying to encrypt messages.

Important note: this answer is only valid for modern ciphers where frequency analysis of the ciphertext is not an attack vector.


Can repeatedly encrypting a message with a secure cipher ever produce the original input like what happens in ROT13? Lets say we have a message 'm'.
We encrypt 'm' using a stream cipher or any other type of cipher with cryptographic security that produces an output equal in length to the length of 'm'.
Then if we keep on on re-encrypting the output with same cipher (but different key each round) for eternity, what are the chances of it ever producing  'm' as the cipher-text.

If the ciphertext is the same size as the plaintext, then yes with 100% probability.
There are only finitely many values the ciphertext can take. So repeatedly encrypting the ciphertext, means that a value must repeat eventually. If this cycle doesn't include the original message, then there is some ciphertext that has an ambiguous decryption (because two plaintexts encrypt to it). Since we know this isn't the case, the original message must be in the cycle.

You can easily tweak this argument to ignore padding (just take the padded message as your original message).
If the encryption scheme requires an IV/nonce, then this argument only applies if you reuse the same IV for each encryption, in other words, after the first encryption, the ciphertext size is constant.
I highly doubt there's a way to show this with an authenticated encryption scheme.


Would LWE problem be still secure if error were like this $e=2e_1$? In the Learning with error problem, if the error term $e$ from equation $b=<a,s>/q+e$ were of this kind $e=2e_1$, where $e_1$ is chosen according to the probability distribution for the LWE problem, it would weaken the problem significantly or the security insured would remain the same ?

It will remain same. Here it will not effect the security because 2 is invertible in the prime q field. In case q is not prime then security will be compromised.


Practical way to generate random numbers from PRNG which are indistinguishable from true random I am working on a project where I want the user to be able to create random data. For that I use a cryptographically random generator (Java's SecureRandom, which uses OS entropy source if available). Additionally I will seed this PRNG with a true 16 byte (or is more needed?) random number (from e.g. random.org). One seed usually only creates less than 1 MB of random data.

Is that a sound approach to generate random data that is indistinguishable from true random data?

Are there any steps to take to strengthen the security? Eg. scramble the seed to make it harder for an attacker who is listening to know what seed was used?

CAUTION: The seeding planned in the question has the potential to remove the default best-effort seeding normally provided by SecureRandom. It will actually do so with some security Providers. Some others will produce true random no matter what.

Worse, the seeding planned might make the output predictable by spying the machine's communication with random.org.

The specification of SecureRandom in Java (1.)5 and down to at least (1.)3 states (emphasis added):

  The SecureRandom implementation attempts to completely randomize the internal state of the generator itself unless the caller follows the call to a getInstance method with a call to one of the setSeed methods.

Java 8 is even clearer:

  If setSeed is not called, the first call to nextBytes will force the SecureRandom object to seed itself. This self-seeding will not occur if setSeed was previously called.

Recommendable practical ways to generate random numbers which are indistinguishable from true random assuming everything works as specified are:

Right after the SecureRandom constructor, perform a single nextBytes with some small numBytes >0 and disregard the result (even though 0 should do if a Vulcan implemented the spec), then setseed with whatever unpredictable data at hand, then use nextBytes.
Do not setseed, directly use nextBytes; but that additionally assumes that the runtime is able to supply entropy.

Method 1 is guaranteed not to lose the default best-effort seed, for in setseed:

  The given seed supplements, rather than replaces, the existing seed.

The above statement is leaving out an implicit and much needed: if any ! Notice that the additional statement:

  Thus, repeated calls are guaranteed never to reduce randomness.

only guarantees that the second and later setseed can't reduce randomness.

This quirk of the Java crypto API is a feature intended for testing: an initial setseed can make tests reproducible. That can be useful. Unfortunately it works, or not, depending on security Providers (at least, and to my knowledge only), and I know no way to tell other than trying. More generally the Java crypto API is complex and occasionally error-prone, to the point that it is hard to be sure that you will reliably get what you want to get, even though casual testing might suggest so.


Are there any standards of multi-prime RSA key generation? FIPS 186-3 specifies a method to generate DSA parameters.

Is there anything similar (official standard or widely-accepted recommendation) that shows how to generate the primes for multi-prime RSA?

Multi-prime RSA (also known as RSA-MP) is supported by PKCS#1v2. This standard supports a public key $(n,e)$ where the modulus $n$ is the product of $u≥2$ distinct odd primes: $n=\prod_{i=1}^u{r_i}$, with $1<e<n$ and $\gcd(r_i-1,e)=1$ (implying $e$ odd). The private exponent $d$ is such that $1<d<n$, and $e⋅d≡1\pmod{\operatorname{lcm}_{i=1}^u(r_i-1)}$. No other requirement on $(n,e,d)$ is given by PKCS#1v2. RSA-MP is $u>2$. Make $u=2$, $p=r_1$, $q=r_2$, and you are back to RSA in PKCS#1v1.

I know no standard about generation of RSA-MP key. However, for advice on the question of the bit size of $n$ and the number of factors $u$, one recommendable paper is Unbelievable Security: Matching AES security using public key systems, by Arjen K. Lenstra. See in particular the synthetic table giving $u:⌈\log_2\min(r_i)⌉$ for a given security level (in bits, with 2K3DES 95-bit), on a given year (with that parameter accounting for the author's evaluation of improvements on the algorithms, but not Moore's law), and according to two models.

Corrected: Following that size advice even at the 2K3DES level (for any entry starting Y2010), adding about $32/u$ bits per year to account for Moore's law (previously forgot that!), and choosing primes of one key randomly, my opinion is there's no need to worry about factorization attacks on that key till the Y2030 limit of that table. Notice that my endorsement assume that an adversary has no significant interest in factoring a single random key among extremely many.

I also like the short and graphical Multi-prime RSA trade offs, although it is restricted to 2048-bit modulus.

The main things to consider regarding $\log_2n$, $\log_2r_i$, and $u$, are:

$n$ should be large enough that GNFS factorization is not to fear. Considerations are just the same for regular RSA and RSA-MP, since the multiplicity $u$ of factors, or their size $\log_2r_i$, does not influence the expected run time of GNFS; only $\log_2n$ matters.
Each $r_i$ should be large enough that $n$ is safe from factorization by known algorithms primarily influenced by the size of a factor extracted (rather than the size of the composite to factor), in particular ECM (among such algorithms, ECM is the most likely to factor one particular key). In regular RSA, it is customary to choose the two primes of equal (or nearly equal) size: this makes it overwhelmingly likely that GNFS subsumes all other known factorization algorithms, including ECM, by a large factor. However, that does not hold for RSA-MP; and while finding one $r_i$ does not by itself make it possible to forge signatures or decipher, it must still be considered a fatal disaster, for GNFS can then tackle the factorization of the composite $n/r_i$ at greatly reduced cost. Therefore, it is customary to choose the minimum size of a factor based on estimation of the running time of ECM (considered a function of $\log_2r_i$, often ignoring the relatively marginal influence of $\log_2n$).
Then the best choice of $u$ is ${\log_2n}\over{\log_2r_i}$, rounded in some direction.

For this, I trust the aforementioned Unbelievable Security.

Details on the choice should take into account that typically $⌈\log_2n⌉$ is prescribed, in which case we'll probably use $\log_2r_i\approx ⌈\log_2n⌉/u$; if not, there is often little or no performance cost in rounding up $⌈\log_2r_i⌉$ up to the next multiple of a word size, like 32 or 64 bits, then use $log_2n\approx ⌈\log_2r_i⌉⋅u$.

It is customary that key generation standards for RSA key pairs add extra requirements in addition to those in PKCS#1v2. FIPS 186-3, a widely accepted standard, has the following requirements in section B.3.1; I'm trying my best to give the rationale:

The public exponent $e$ shall verify $2^{16}<e<2^{256}$. The lower bound is here because some attacks on poor RSA-based schemes are often easier when $e$ is small; the higher bound is for interoperability of public-key operations.
The bit size of $n$, $nlen=⌈\log_2n⌉$, should be 1024, 2048, or 3072 (note: in appendix B.3.1 of FIPS 186-3, the are references to 1024-bit, 2048-bit and 3072-bit primes; that shall be understood as the bit size of $n$, although that is composite). The limited choice maximize the critical interoperability of public keys; the lower bound also enforces a baseline security (according to NIST Special Publication 800-131A, for signature generation, 1024-bit is acceptable through 2010, deprecated from 2011 through 2013, and disallowed after 2013); the lack of 4096-bit or more is seen by some as an indication that ECDSA is the way to go.
The prime factors $p$, $q$ of $n$ shall be in range $[2^{(nlen-1)/2},2^{nlen/2}]$; this is primarily to ease interoperability of private keys across implementation.
$|p–q|>2^{nlen/2–100}$; this is a legacy of ANSI X9.31, where AFAIK it was introduced as a simple way to repel the rhetorical argument "but even Pierre de Fermat knew a factorization algorithm that could defeat RSA".
Primes $p$ and $q$ shall be chosen at random using the same algorithm (with $e$ an input), chosen among a few approved algorithms, falling into two main categories (random primes, and random primes with condition, with subdivisions depending on if the primes are probable or provable primes). This avoids poor algorithms, prevents optimizations of $d$, $dP$, $dQ$ giving questionable security, and eases validation of implementation, even allowing Known Answer Tests.
These approved algorithms are such that for $p$ of 512-bit, $p-1$ (resp. $p+1$) shall have a prime factor $p_1$ (resp. $p_2$) of more than 100 bits; same for $q$; if a similar condition is used (that's optional) for $p$ of 1024-bit (resp. 1536-bit), that should be more than 140 (resp. 170) bits. These requirements are intended to give insurance against Pollard's $p-1$ and William's $p+1$ factoring algorithm.
These approved algorithms come with a maximum size of the primes $p_1$ and $p_2$ discussed in (6.) AFAIK this just precludes choosing these primes $p_1$ and $p_2$ so big that the choice of primes $p$ is reduced to a point where this becomes an issue.

If I had to propose an adaptation of FIPS 186-3 for generating RSA-MP keys, it could be:

Unchanged (though personally I would choose $e=2^{16}+1$; and if you ask, I'd ease the lower bound to $e=3$, with no security impact when good schemes are used; but  that's independent of RSA-MP).
$nlen=⌈\log_2n⌉$ among 1024, 2048 or 3072 for full interoperability with FIPS-based signature verification devices; or changed to $1024≤nlen≤16384$ with $nlen≡0\pmod{64}$ on condition of agreement with potential signature verifiers, for more flexibility and future-openness. Recommendations on $nlen$ and $u$ based on the Unbelievable Security reference above, although with $u≤nlen/512$ no matter what.
Adapted to $2^{64⋅⌊(nlen/64+i−1)/u⌋-1/u}<r_i<2^{64⋅⌊(nlen/64+i−1)/u⌋}$. This ensures $⌈\log_2r_i⌉≡0\pmod{64}$, $⌈\log_2\prod_{i=1}^u{r_i}⌉=nlen$, and at most two different $⌈\log_2r_i⌉$.
Replaced by a test that any two $r_i$ differ in at least one of their 100 high-order bits (more in order to catch faults than for fear of Fermat factoring).
Kept for algorithms in the "random primes with condition" categories, with only the parameters of the approved algorithms adapted; see justification in (6.) below.
Kept, with the requirement that $⌈\log_2p_1⌉$ and $⌈\log_2p_2⌉$ are more than $60+5⋅⌈\log_2p⌉/64$. This linearly scales the value 100 and 140 in FIPS 186-3, and removes the option to ignore that for $⌈\log_2p⌉>1024$ by using an algorithm in the "random prime" category. My opinion is that this requirement makes sense in the context of RSA-MP: a rational adversary content with factoring any of many modulus (rather than factoring a particular modulus) should not start to use ECM on one or a few modulus; but rather should first try Pollard's p-1 on all the modulus, as the ECM strategy has a markedly lesser chance of success for a given effort (argument: Pollard's p-1 is used with great benefit by state-of-the-art factoring programs such as gmp-ecm; also see this related answer).
Kept; this really is just not changing the approved algorithms.


Deep Learning application in decryption? If the output of an algorithm when interacting with the [encryption] protocol matches that of a simulator given some inputs, it ‘need not know’ anything more than those inputs.

Can a machine learn to find a method to break encryption protocols?
How is that possible, to decrypt ciphers using deep learning methods?

There is no evidence of deep learning breaking modern cryptography. Deep learning is simply glorified gradient descent.
With a reasonable cipher you get no indication of almost finding the key, so I see no hope of deep learning breaking a black box cipher.

In order to use deep learning for cryptography we would need to find a notion of gradually or partially solving the problem, not an easy task.

We have seen some work to use deep learning to build new ciphers, using adversarial training. But there is not much evidence these ciphers are secure against human cryptanalysis.


Is including the key as AAD actually dangerous? In a recent answer, Maarten mentioned

  including the key is a bad idea as well.

This got my curious. Is there any scientific / cryptographic analysis whether including the key in the authentication actually allows for (easier) attacks in the standard model(s) for authenticated encryption?

Obviously this means that both sides include the key in the AAD but don't send it in clear.

I also see that it's kinda pointless to include it, but is it actually dangerous? (less formal than above)

If no generic answer is possible, please assume AES-GCM as the scheme in question

One potential issue with GCM is that it can potentially make the problems you get from repeating nonces worse; instead of allowing you to forge, and revealing the plaintext for the packets with the repeated nonces, it can become a key recovery issue.

Here's one way it can happen; suppose the AAD is the 128 bit key, and you repeat the nonce with three different messages of different lengths (a 1 block, a 2 block and a 3 block message).  Then, the three GCM tags are computed as:

$$KH^3 + C_1H^2 + C_2H + Y = T_1$$
$$KH^4 + C_3H^3 + C_4H^2 + C_5H + Y = T_2$$
$$KH^5 + C_6H^4 + C_7H^3 + C_8H^2 + C_9H + Y = T_3$$

where $K$ is the unknown key, $H$ is the unknown $H = E_k(0)$ value, $Y$ is the unknown value $Y = E_k(nonce)$ used to protect the tag (and because all three messages use the same nonce, they have that value in common), and $C_1, ..., C_9$ and the tag values $T_1, T_2, T_3$ are values known to the attacker.

These are three polynomial equations in three unknowns; they can be combined into a single fourth degree polynomial in $H$ (and not $K$ or $Y$); it can be solved for $H$ (giving up to 4 possible solutions), from that, you can recover the secret key $K$ value as one of 4 possibilities.


Choice of padding scheme to prevent CBC padding oracle attacks? I was watching a lecture about the padding oracle attack on CBC mode block ciphers, where the padding scheme used was PKCS#7.

My question is can padding oracle attacks be prevented (without any use of a MAC) solely by choosing a suitable padding scheme?

In the lecture, the attack first finds what the actual padding of the plaintext will be. I assumed that the rest of the attack outlined in the lecture worked only because PKCS#7 is a predictable padding scheme. Which means that once the adversary gets a BAD_PAD error, he will know that there is only one possible pad that will be the correct pad.

If the padding scheme used is unpredictable, would the CBC mode be secure against padding oracle attacks?

I was thinking of the following padding scheme:

Choose distinct and random bytes X and Y, which will be different every time you encrypt a message. Pad with X and at least one copy of Y. So if the block length is 8 bytes and your message is ABCD, you can pad the block to be ABCDXYYY, ABCDXXYY, or ABCDXXXY.

Would this padding scheme prevent padding oracle attacks? Because now when the attacker gets a BAD_PAD error, he will not know for sure what the correct pad should be.

Padding oracle attacks are not the padding scheme's fault! They are not fixed by changing the padding! They are fixed by not leaking partial information about the result of decryption, or (preferably) by just using CCA encryption.

Any time you provide this to an adversary:

* Accept arbitrary c
* Decrypt m = Dec(c)
* Reveal formatcheck(m)

... if it's only a CPA-secure encryption scheme, you undermine all security of encryption. The specifics of the format check don't much matter. Some padding schemes (more generally, "format checks") can make a plaintext recovery attack more or less direct, but all will undermine overall security to some extent.


Why restrict nonce/IV and counter to specific sizes? When setting up a nonce/IV and counter (e.g. for AES-GCM-128), why are the nonce/IV and counter restricted to specific sections (e.g. random nonce/IV in first 8 bytes and counter in last 8 bytes)? This results in the last 8 bytes always starting off at a predictable value (0), reduces uniqueness (only 8 bytes of random data), and requires more frequent re-keying due to counter wrapping.

Is there a reason the entire 16 bytes cannot be initialized to random data, start the counter from there, and allow the counter to use the entire 16 bytes?

The answer is that you can do exactly what you say. Initialize the counter to a random 16 byte number and start counting. Wikipedia (not sure if that is where you got the idea that it must be 8 bytes and 8 bytes) has the following note:

  The IV/nonce and the counter can be combined together using any lossless operation (concatenation, addition, or XOR) to produce the actual unique counter block for encryption.

There is some benefit to separating things though. For example, splitting it into 8 bytes and 8 bytes, as long as you never generate the same 8 byte nonce/IV while using the same key, your encryption stream will never repeat. Further, you know exactly how many nonces/IVs you can generate before expecting to see a repeat ($2^{32}$ from the birthday paradox) with about a 0.5 probability. In a submission to NIST by some very reputable cryptographers, this method of doing CTR mode was called "the recommended usage scenario".

Lets instead assume you generate a 16 byte nonce/IV and just start incrementing it. What happens if two nonces/IVs have a difference of 1000 (i.e., $|n_1 - n_2| = 1000$). Well, after encrypting 1000 blocks (with the same key) you will now be using the same encryption stream. Analyzing this is a bit more tricky as you need to know the probability of generating two nonces that are within some range of each other (the range being determined by how many blocks you will encrypt). Depending on the application this could be a major problem. My guess though is that in the majority of applications it isn't a problem.


Combining secure hashes with insecure hashes? Assuming I'm a bank which seeks for secure hash functions to use in the process of  signing on digital contents.

I'd like to explain / prove why using each one of the following hash functions might be less secure than using SHA-1 (yes, I know SHA-1 no longer considered secure, but the question does consider it as one, or at least states "do not be less secure than sha-1").

$h_{666}(m) = $ some new hash function with 666 bit long output.
$h_{ib}(m)=h_{sha-1}(h_{md5}(m))$
$h_{hm}(m)=h_{md5}(m) \oplus h_{sha-1}(m) \oplus h_{ib}(m) \oplus h_{666}(m)$, while the XORing operation here xors the matching bits between two outputs, padding with 0s the smaller ones.

I would say…

I can tell that using new hash function is a bad idea since no one has yet to research and attack it, aside from the fact that more bits is less efficient. Apart from this explanation, I don't see other reason to disqualify this answer.
md5 is broken and collisions can be made quite easy, so two different inputs to this function can collide and have the same input to the sha-1 function, which will result in collision between the final outputs.
I have no clue how to disqualify this one. The intuition says 'xoring with bad hash functions is not a good idea', but I can't really justify my answer.
I also think the padding doesn't actually affect anything, becuase if SHA-1 result is secure then padding 0s to it won't make it collide with other inputs suddenly.

Am I correct, or did I miss something obvious somewhere?

Edit

This is different from “Guarding against cryptanalytic breakthroughs: combining multiple hash functions” since here the idea is to combine unsecure hash with a secure one. This is not about just combining hashes.

I can tell that using new hash function is a bad idea since no one has
  yet to research and attack it, aside from the fact that more bits is
  less efficient. Apart from this explanation, I don't see other reason
  to disqualify this answer.

That one is largely correct, although more bits doesn't have to mean "less-efficient" as for example Skein-512 turned out to be faster than Skein-256 during the designer's tests.

  MD5 is broken and collisions can be made quite easy, so two different
  inputs to this function can collide and have the same input to the
  SHA-1 function, which will result in collision between the final
  outputs.

This one sounds good.

  I have no clue how to disqualify this one. The intuition says 'xoring
  with bad hash functions is not a good idea', but I can't really
  justify my answer. I also think the padding doesn't actually affect
  anything, becuase if SHA-1 result is secure then padding 0s to it
  won't make it collide with other inputs suddenly.

This one is actually quite interesting. The property in question here is pseudorandomness of the output. If you zero-pad, the shorter hash functions don't have an effect on the higher bits, so MD5 will only enhance the first 128-bit, SHA-1 and $h_{ib}$ will only enhance the first 160 bits and the remaining 506 bits are up to $h_{666}$. Now if $h_{666}$ isn't pseudo-random, neither will this construction (likely) be, because you can distinguish the output from a random value using only the 500 high bits, which is obviously bad, as we already established that $h_{666}$ isn't exactly trust-worthy.


Do all attacks against PKCS1 v1.5 encryption require an oracle As far as I know, all attacks against RSA PKCS1 v1.5 require an oracle; is that true? Or are there any other attacks against it which are able to break it without an oracle?

Background: I need to support PKCS1 v1.5 because most crypto-devices sadly don't support OAEP. However, the software is only used for manual file en-/decryption, so there is not an oracle available.

PKCS#1 padding succeeds in introducing enough entropy (slightly less than 64 bits at the very minimum) to make RSA encryption semantically secure. Furthermore, the number $m$ - the message used for modular exponentiation - it produces will be large enough to protect against attacks that rely on $m$ to be small. That means that the premisses for RSA modular exponentiation seem to be met.

It seems therefore unlikely that there are passive attacks on PKCS#1 v1.5 padding. Active attacks could succeed, as Bleichenbacher has shown. It may be that there are attacks on the random number generation as well, but that will require an attacker to have even higher privileges; the attacker must have access to the secure random number generator used. Usually those kind of attacks are considered attacks on the secure system creating the ciphertext itself instead of attacks on the algorithm itself.

Finally there are side channel attacks on modular exponentiation, but those are as much a problem for OAEP as for PKCS#1 v1.5 padding. They also rely on the attacker gaining more knowledge from the system than should be allowed for a secure system to exist.


What does "congruent to 448, modulo 512" mean for padding in MD5 hash function? What does "congruent to 448, modulo 512" mean within the MD5 hash specifications?

From the specification:

  The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo 512. That is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long. Padding is always performed, even if the length of the message is already congruent to 448, modulo 512.

When we talk about a number $x$ being "congruent to 448 modulo 512", what we mean is that $x$ modulo 512 and 448 modulo 512 is the same number; since 448 is less than 512, this is equivalent to $x \bmod 512 = 448$

So, how the padding in MD5 works is "first you append a 1 bit (this part isn't mentioned in the above quote, but it's a necessary step), and then you keep on appending 0 bits until the total length of the message (mod 512) is exactly 448 (and then you append the 64 bit length of the unpadded message, in little endian order).

And, if you are only in hashing messages that are integral number of bytes (e.g. you don't care about the hash of a 123 bit message), then the equivalent procedure is "append an 0x80 byte, then then keep on appending 0x00 bytes until the total length of the message in bytes mod 64) is exactly 56 (and then you append the 8 byte length of the unpadded message).

Note that, in both cases, if the message after appending the 1 bit/0x80 byte is exactly 448/56, then you don't append any 0 bits/bytes.

Also, the SHA-1 and SHA-256 hash both use the same padding method (except that the byte length is in bigendian order)


Identifying and attacking a proposed cipher (multiple substitution) I'm just beginning to dip my toes into cryptography and a friend has proposed a cipher and challenged me to figure out how to attack it.  I know the process used to encrypt, but am having a hard time wrapping my head around a way to go about attacking it.

The cipher is a simple substitution cipher (26 characters possible, each character directly mapping to one other character) and the text is evidently plain ole English.  The complicating (at least to me) factor is that in his process he performs this substitution N times where N is the index of the character.

ex.
plain text = "test"
  alphabet = "abcdefghijklmnopqrstuvwxyz"
       key = "bdfhjlnprtvxzywusqomkigeca" (permutation of alphabet)

plain[0] = 't'                       (1st char subs 0 times, so remains 't')
plain[1] = 'e' -> 'j'                (2nd char subs 1 time, becomes 'j')
plain[2] = 's' -> 'o' -> 'w'         (3rd char subs 2 times, becomes 'w')
plain[3] = 't' -> 'm' -> 'z' -> 'a'  (4th char subs 3 times, becomes 'a')

encoded = "tjwa"

Does this cipher have a name?  I'm having a hard time finding one online if it does.

As for attacking it, he has given me a large encoded string (100k+ chars).  I wrote up a simple Java program to perform encode/decode given a known key, but 26! keys are too many to brute force.  So I looked at the letter frequency and noted that a single letter (in my case 'x') appears a disproportionately low number of times (much closer to it's expected English frequency the the other characters), which leads me to believe that perhaps it maps to itself. But obviously that would still leave 25! keys.

I'm genuinely interested in figuring out other techniques to attack this, and am not asking for a single simple solution, but does anyone have any ideas of other ways to go about attacking it?  I know the first letter of the plain text, and possibly the positions of a single other letter, but possible "cycles" or "loops" (sorry, I don't know if there's a better word for this) within the key (a->b->c->a) are thus far stumping me as to how to attack it.  I at first thought I'd know every 26th character, but that would only be true if there were no "cycles" created by the key.

Any help/direction/pointers/suggestions would be appreciated. Thanks.

The obvious way to approach this would be to attempt to recover the cycle structure of the permutation, and the first place to start is to attempt to reconstruct the order of each letter.

The "order" of a letter is how many times the permutation needs to be applied to the letter before it turns back to that letter.

To start, you believe that you have the matting x -> x; that means that the order of the letter 'x' is 1.

Let us extend that idea, if we have the mapping e -> w -> g -> e, then the order of the letter 'e' (and 'w' and 'g') is 3.

So, how do we estimate the order of a letter?  Well, we start be looking at every 'n'th letter of the ciphertext (that is, positions 0, n, 2n, 3n, etc); if the order of a letter is n (or a divisor of n), then in those positions, that letter will map to itself (and so the character frequency in those positions of the ciphertext will be exactly the character frequency in the plaintext); assuming that the plaintext is English text, it should be fairly straightforward to come up with plausible guesses.

Once you've tried that, and have come up with plausible guesses for the orders of all the letters, we then need to reconstruct the 'cycles' that make up the permutation.  The first obvious place to start is to find the element that e maps to; if we have found that the order of e is 3, we can start by looking at every 3rd element offset by 1 (e.g. at locations 1, 4, 7, 10, 13, etc); in those locations, 'e' will encrypt to whatever letter it is permuted to, and so if in those locations, the letter w happens exceedingly often, we can deduce that e -> w is a likely mapping within the permutation.

Those hints should give you a good start...


Diffie-Hellman key exchange using addition instead of multiplication? I know that the additive finite group $(Zp,+)$ of prime order $p$ when I perform the Diffie-Hellman key exchange (DHKE) protocol is insecure. I didn't however find many sources online explain why it is insecure. Neither could I find information about what possible attacks can be performed in that case.

Can anybody explain why it is insecure and what possible attacks would be possible if I would use addition instead of multiplication?

Additionally, how can I make both Alice and Bob have the same key when performing the DHKE using $(Zp, +)$?

Why can't we use $(Z_p,+)$?

In the DH key Exchange Alice and Bob agree on a common generator g which allow to share a common key. In fact in $(Z_p,+)$ every non zero element is a generator.

If a common generator g is preallably chosen, when Alice chose a secret a, transmitting A=g.a, the secret a will be immediatly disclosed by any one in the public channel by simply Computing $a=\frac{A}{g}$ and key exchange will be violated which isn't the case in $(Z_p,*)$, as the inversion by the discret logarithm, is considered hard.


Zero knowledge set membership protocol I read that paper Efficient Protocols for Set Membership and Range Proofs of Camenisch et. al that describes the zero knowledge range proof. The paper applications looks interesting like if you want to proof your age between a range without stating exactly what is the exact age?

But I read that a commitment (C) provided by the prover to the verifier should be first verified by a trusted party before it can be used in the zero-knowledge protocol? Is it just a signature on the C value?

I need a simple explanation of how such a commitment can be done. Since as far as I know about a commitment (C) that is only known for only one party.

A trivial approach would be to let the trusted party generate the commit and send the private vector along the signed commit to the proover, which should like this in your age range checking example:

Notation:
$P$ is the proover, $T$ is the trusted party, $V$ is the verifier, $a$ is the information to convince $T$ of $P$'s age, $A \rightarrow B: x$ means that party $A$ send information $x$ to party $B$.

$P \rightarrow T$: $a$
$T$ generates chooses a random $r$, calculates $C=rG+[age]H$ and signs $C$ using his private key.
$T \rightarrow P$: $r, C, signature$
$P \rightarrow V: C, signature, proof$

Whilst straightforward, the trusted party get's to choose the commit which you may not want depending on how much you trust the trusted party, so here is another approach that allows the proover to choose $C$.

$P$ chooses a random $r$ and calculates the commit $C = rG + [age]H$.
$P$ signs $a$ with $r$ as private key
$P \leftarrow T: C,a, signature_a$
$T$ looks up $P$'s age, calculates $R=C-[age]H$, verifies $signature_a$ against $R$ and sign's $C$ using $T$'s private key.
$T \rightarrow P: signature_c$
$P \rightarrow V: C, signature_c, proof$

Of course, $V$ will have to verify the signature. Instead of a signature, $V$ could also make a request to $T$ to check whether it approves $C$ which allows $T$ to revoke easily but requires you put more trust into the trusted party.

Lastly, I'd like to mention a completely different approach used in Monero's RingCT which uses commits to represent balances and the blockchain to keep track of and to verify them.


Secret sharing over $Z_n*$ Shamir's secret sharing protocol generates a polynomial over a prime field $F_p$.

Is it possible to generates it over $Z_n^*$ as well?

The reason is that I want to combine a secret shared value in another scheme. For example sign on it with an RSA signature (that is over $Z_n^*$.

Thanks.

If you just want to sign the shares like you said, then you don't need the shares to be in $Z_n^*$. You can just share over $F_p$ as usual. To sign a message, usually the message is hashed first and then the hash value is fed in the signing/verification algorithms. Therefore the fact that the shares are in $F_p$ will not affect signature generation and verification.

Shamir's secret sharing cannot be over $Z_n^*$ because $Z_n^*$ is not closed under $+$. But there are other secret sharing schemes over $Z_n^*$. As an example, the simplest one is this:

to share a secret $s \in Z_n^*$, choose $r_1,\ldots,r_{t-1}$ uniformly at random from $Z_n^*$.Compute $r_0 = s\cdot \frac{1}{\prod_{i=1}^{t-1} r_i}$.
Now you have $t$ shares $r_0,\ldots,r_{t-1}$, and you can distribute them to $t$ parties.
To reconstruct the secret, multiply all shares together and you get the secret $s=\prod_{i=0}^{t-1} r_i$.


What are the steps to decrypt a TLS 1.1 record? My question is related to another question in Cryptography about TLS 1.1 and 1.2. I have read both RFC 2246 The TLS Protocol Version 1.0 and RFC 4346 The TLS Protocol Version 1.1. What I know is that one of their differences is TLS 1.0 uses implicit initialization IV (from the key_block) and TLS 1.1 uses explicit IV, which can be generated with either of the three ways specified in Section 6.2.3.2 of RFC 4346. In the same section, it is stated that

  The decryption operation for all three alternatives is the same.
  The receiver decrypts the entire GenericBlockCipher structure and
  then discards the first cipher block, corresponding to the IV
  component.

The above statement is not clear to me. For example, if I have an encrypted message consisting of blocks [Encrypted Block 1], [Encrypted Block 2], ..., [Encrypted Block n], does that mean that when decrypting, I should discard [Encrypted Block 1] from the other blocks and decrypt [Encrypted Block 2], ..., [Encrypted Block n] using [Encrypted Block 1] as IV?

Is the above example correct? If not, how can the IV to be used for decryption be determined?
Is the decryption for TLS 1.1 the same as TLS 1.2?

Is the above example correct? If not, how can the IV to be used for decryption be determined?

Yes, it is correct. The vector/mask in CBC mode is generally the previous ciphertext block. The algorithms in 2a and 2b simply extends this notion to the IV so that the CBC mode encryption doesn't have to be re-initialized. The outcome of the IV decryption won't have any meaning, it's the ciphertext block itself that is reused.

In dumb implementations of CBC / block ciphers the re-initialization may take time because it may replay the subkey derivation for the cipher. In general though using the first block directly as IV will be more efficient because it skips one block decrypt.

  Is the decryption for TLS 1.1 the same as TLS 1.2?

Yes, see below:

opaque IV[SecurityParameters.record_iv_length];
          block-ciphered struct {
              opaque content[TLSCompressed.length];

although described somewhat differently the IV length is the same as the size of the block for CBC. It is directly followed by the "opaque" (encrypted) content.


How can Shor's Algorithm be applied to ECC? I have not found a specific answer to this question on here.

Shor's algorithm can be used to factorize a large (semi)prime $N$ by reducing the task to period-finding of a function $f(x)=x^a$ mod $N$.

This is done by creating an equal superposition over all pairs of $a_i$ and $f(x)=x^{a_i}$ for a random $x$, then measuring $f(x)$ causing the superposition to collapse into all $a_i$ for which $f(x)$ is our measures value. Using "Fourier sampling" (I have not fully understood this part) we can then obtain the period of  $\ f$ and with .5 probability this yields a non-trivial square root of $N$ which leads to a prime factor.

(Plase correct me if my understanding of the above is flawed)

Now how can this algorithm be applied to Elliptic Curve schemes like ECDSA? I struggle to find an explanation for how the discrete log problem for groups over elliptic curves could be solved using Shor's.

EDIT: I would just as well appreciate a reference to other papers except Shor's, that explain the case of Shor's algorithm on DLPs.

Section 2.2 of the following paper details how to apply Shor's algorithm to ECDLP: https://eprint.iacr.org/2017/598.pdf

The process is similar to DLP, except that we need different circuits to perform our our group operations in elliptic curves (additions and scalar multiplications).


IV transmission from Transmitter to Receiver side in CTR mode for every call I am using block cipher mode (CTR Mode) for the transmission of voice data. Need to know, how can I transfer the same IV at the decryption side (for every call) as the IV for the same packets on encryption and decryption sides must be the same.

If you encrypted your data as $c = \mathrm{CTR}_{IV}(m)$ you can send the value $IV || c$ (where $||$ is concatenation) to the decryption side. That side then parses the value it received into $IV$ and $c$ and computes $m = \mathrm{CTR}_{IV}(c)$. No need to keep the $IV$ secret.