Simple RC4 key generation scheme I would like to ask you about your opinion on the following scheme of combining a master key and a nonce and stretching the result to the full 256-bytes RC4 key.

Master key $K_m$ is a pre-shared secret of length $M$ bytes
nonce $K_n$ is sent unencrypted and is of length $N$ bytes
both $K_m$ and $K_n$ are chosen to be high-entropy strings
the $i$-th byte of the resulting key would be $K[i] = (K_m[i \bmod M] + K_n[i \bmod N]) \bmod 256$

The period of the string $K$ is $LCM(M,N)$, so I would choose the $M$ and $N$ such that $LCM(M,N) \ge 256$.

Is there anything obviously wrong with this scheme?

PS: This scheme would be used on an 8-bit micro-controller embedded system. Limited speed/memory prevents me from using a more standard method.

I am familiar with the RC4 related key attacks; I can say that if you publish the nonce, and use any of the first 256 bytes of the RC4 keystream, that you are vulnerable to those attacks.

These attacks exploit a correlation between specific bytes of the RC4 key, and the initial output values; with your approach, the attackers can guess what (say) byte 2 of the master key was (by computing what the corresponding RC4 key is for each message, and checking to see if the RC4 byte statistics is what he'd expect); this would allow him to recover the entire master key with enough messages.

I would strongly urge you that, if you can't follow D.W. advice, and you have to live with this scheme, that you always discard the initial (at least) 512 bytes of the RC4 keystream immediately after you rekey RC4.  Why 512 and not 256?  Well, some statistical analysis shows that byte 258 of the generated keystream has a measurable bias towards the value 03; it is unknown why it is, or if it has any correlation with the initial key; but it is a bad sign.


Hashing based on the discrete logarithm problem At a first look, one could use the elliptic curve discrete logarithm problem to grant for the onewayness of $H(x)=x*G$ (where $G$ is the generator point of the cyclic subgroup).

Additionally, $H(x)$ is homomorphic since $H(x+y)=H(x)+H(y)$, which could prove to be a useful property for a hash function in some applications.

What are some of the disadvantages or vulnerabilities that makes such a hashing scheme not popular in practice?

A secure hash function based on the discrete log problem is $H(x\|y)=x\cdot G+y\cdot P$, where $P$ is a random point for which the discrete log is not known and "$\|$" denotes concatenation; this was shown by Damgård. This can be proven collision resistant under the discrete log assumption (if you can find a collision then this can be used to find the discrete log of $P$). Note that in order for it to be of interest, the output has to be shorter than the input. However, this is easily achieved for most curves by using point compression. Once you have this function, you can get a general collision-resistant hash function by applying the Merkle-Damgård transform.

Of course, this would be extremely inefficient, but it is a collision resistant hash function from the discrete log problem.

The paper presenting this is Collision Free Hash Functions and Public Key Signature Schemes by Ivan Damgård. It is also described in Section 8.4.2 of the Katz-Lindell textbook (second edition).


Why use base64 or hexadecimals for ciphertext? They are asking me to deliver encrypted text in ISO/IEC 8859-1. I have always encoded it to hexadecimal or base64. This text will be sent in a file with plaintext and encrypted text. In my opinion it won't work because of the non-visible characters.
I also wonder if there are characters that exist in hexadecimal and not in ISO/IEC 8815-1 (Western-Latin encoding). Am I right in assuming so?

When using standard encryption algorithms like AES-GCM, ciphertext is bytes that are approximately uniformly distributed among the 256 possible byte values. Since ISO/IEC 8859-1 allows like 191-byte values out of 256, it's extremely unlikely that any practical ciphertext will entirely consist of these 191 bytes, as would be the case if some appropriate Binary-to-text encoding was used, including Base64. In the rest, I'll assume it is not used such encoding.

The curious case is that within that file there are two lines in plain text (header and footer) and the rest encrypted.

That does not make it impossible for decryption of such files to works. Many modern file transfer methods, including USB thumb drives, attachments to email or messaging, network shared volumes, cloud storage, UNIX pipes, windows pipes opened in binary mode… will happily transfer any (contiguous and single fork/stream) file with all its data (if not metadata like file name, date and security attributes) unchanged. Thus the problem of allowing decryption boils down to locating the ciphertext in the file.
That can be dealt with with conventions. One possibility is that ciphertext starts after a header of fixed size in bytes that the decryption skips. Another is that it starts after the first occurrence of a fixed text sequence, e.g. <-- ciphertext on next line --> followed by a single LF character. The end of ciphertext can be dealt with by embedding the ciphertext length at the start of ciphertext. That can work if the file is correctly prepared, e.g. by a correctly written program; or by manually concatenating a header file, the ciphertext, and the footer file using bash on a Unix system; or using copy /b of cmd.exe on Windows.
Things that go wrong when that's attempted include: the file is opened and mistakenly saved with a text editor (perhaps to remove the header), and that particular text editor ruins the ciphertext (many do); the sender used CR LF as end-of-line and the decryption is unaware of that; the file is piped to a console display emulating some glass terminal (e.g. a VT100 itself emulating an ASR-33), which emits silly noises, locks, or act strangely because it entered an obscure mode.


Block cipher swap key and message Say I use AES. If I insert the message the way the key normally is used and vice-versa, would this be equivalent secure to the intended encryption?

From a theoretical perspective - speaking of general pseudo-random permutations (PRP, the theoretical model used for block ciphers) - no.
An examples: Let $F(k,m)$ be any secure PRP.
Then $F'(k,m)=\begin{cases}m&\text{if }k=0^n\\F(k,m)&\text{else}\end{cases}$ is a secure PRP as well as the chance of actually randomly picking $0^n$ is negligible. Of course once you use more chosen strings for the key - as you'd when swapping the inputs - this guarantee breaks down and you need further guarantees from your cipher for security to hold.
This is not a property known to hold for AES, but the AES key schedule is known to not be the most robust when not choosing random keys, so caution is strongly advised.
Also on a performance note: AES key generation is slow and would be required for each message block in this scenario, increasing the computational cost by 3-10x depending on the implementation.


Order of multiple encryption algorithms as you can see on image above, in VeraCrypt you can select either

Serpent -> Twofish -> AES

or

AES -> Twofish -> Serpent

what's the point of those permutations? is there any difference if I use

A -> B -> C

or

C -> B -> A

combination of encryption algorithms?

Yes, in case of VeraCrypt there is a difference, but it is negligible in practice.

First we need to consider how VeraCrypt actually performs the cascading of the encryption algorithms which is (literally) a block-wise chaining. E.g.:

$$C=E_{XTS}^{1}(E_{XTS}^{2}(E_{XTS}^{3}(M)))$$

where each $E$ is a block cipher run in XTS mode and all using the same XTS parameters in the same position. Of course, keys for each block cipher are still independent, resulting in 1536-bit of key material ($=6\times 256$, XTS uses 2 256-bit keys by itself and each XTS instance has its own keys).

Now the difference of order comes into play when we consider the following result in particular:

  [...] a cascade is at least as difficult to break as the first component cipher.

 From the abstract of: "Cascade Ciphers: The Importance of Being First" by Maurer and Massey (PDF)

So obviously you want the cipher you trust the most in the first position and this is the whole reason why you are given the choice of the order here.

Note however:
Actually using triple encryption is a waste of resources as none of the available ciphers has yet been (notably) broken when independent keys are used and brute-force is already out of the reach for any attacker even if the key-length is "only" 256-bit.


What does "circuits" mean in Cryptography? I am not a hardcore cryptographer so this might be a really stupid question. I am looking through some papers in homomorphic encryption and discovered they describe computation as "circuits", why do they use this particular term? Isn't algorithm a more suitable word? Do "circuits" have some special meaning in cryptography?

Circuits can be expressed using very simple operations. For example, a boolean circuit consists of only two types of gates, addition and multiplication (where the input values are each 1 bit). Furthermore, (boolean) circuits can describe any computation.

This is very nice when it comes to fully-homomorphic encryption. All we have to do is provide a way to homomorphically evaluate two types of gates and voila, we can evaluate any computation homomorphically. As pointed out in a comment below, circuits have been used for more than just homomorphic encryption. Secure multiparty computation (both the secret sharing and the garbled circuits variants) uses this as well.

This makes the job for cryptographers much easier, but makes things harder on users, right. If I want my super awesome algorithm to be evaluated homomorphically, I've got to come up with a way to implement it as a boolean circuit. That means no loops, no conditionals, etc. I only get addition and multiplication. Other computation paradigms have been looked at. One early one was moving from boolean circuits to arithmetic circuits (not too big of a jump).

Update
Recent work is interested in not limiting programmers to circuits. For example this, this, and this all look at language based approaches.

P.S. Sorry for the link dump. I haven't properly read through these so I can't really comment. A question on how non-circuit approaches work could be a good question to ask. I'm betting there is someone on here who can go into detail on those.


Is there a way to tell if a given string is a sha256 hash? Just like, for instance, we can easily check if a given number is a visa card number, by verifying prefix and checksum - can we do anything similar for hash?

Hashes have no defined structure as e.g. IBAN bank account numbers, to follow your example (not sure about the case for credit cards).

The output of SHA is essentially a number value, without checksums or other additional elements.

To answer your question, the only check you can perform is to verify that the potential SHA-256 hash is 256-bits long. In fact, since you can feed arbitrary inputs into the algorithm, any 256-bit value will be a correct SHA-256 hash for some input(s).

Since you mention strings as the datatype to check: note that the “string” hash is commonly a minimal hexadecimal representation of said hash. The minimal form of hexadecimals consists of two digits per byte, where each digit is a character ranging from 0 to 9, a to f or A to F.

So if your candidate string contains any other letters/symbols it can be rejected. This is a trivial check that lets you distinguish between (2 * 32 = 64) hexadecimals and other text - it doesn't proof that the bytes are the output of a hash function.


Can I encrypt user input in a way I can't decrypt it for a certain period of time? I run a baseball league and would like to do silent auctions for free agents.  This would require teams to enter their highest bid and the highest bidder at the end of the auction period would win.  Unfortunately, my league, my code, my server, I have access to the information if I choose to look at it.  I'd like to not put myself in that position and have that information available.

Is there any way I could encrypt the inputed data so that I can't unlock it for a specific amount of time (2 days)? Is this possible?

An alternate way of doing it would involve md5'ing the users input, but that would require them to come back and 'unlock' their bid.  I don't like this b/c if a player gets injured after their bid, they'll 'forget' their bid and not unlock it...

I'm running LAMP/LAPP.

UPDATE - Solution (for my case...)

To answer the question of league trust, there are three factors.

will I cheat?  the smallest issue I actually have b/c I don't think I will
will the league think I cheated?  it doesn't matter if I do if them thinking I do causes an issue
if a donut is sitting on the table you can choose to not eat it, but you'd rather it not be sitting there.  even if you can restrain yourself, it isn't always pleasant to do so.  I'd like to think I wouldn't actually cheat, but don't want to have to restrain myself.

Solution:

It seems there isn't a good general solution to this problem.  Several of the solutions required a fair amount of technical knowledge from the majority of the league, which unfortunately, isn't the case - but there are 2 other programmers in the league.  Here's what I'm settling on:

I'm extending the auction from 2 days to 3 days.  I'm going to bid in the first day and md5 my bid with a salt "jibberish-text-salt-3.5M" and display that encrypted text on the auction page.  I won't change my bid after that, others can bid over the next 2 days.  At the end of the auction, I'll post my salted bid so the other programmers can confirm I haven't cheated.  Anybody else that is concerned can learn to use md5, I feel I've done enough to keep myself honest at this point.

Without being able to change my bid, and being forced to bid early, I'm at a slight disadvantage - a player could get injured, etc.  To even this out, I'm instituting an option for me to appeal to the league that my bid be canceled should something huge happen (since I would wait until the last minute otherwise to prevent this from happening).  The league will then vote on it.  There's also the possibility that someone I'm not interested in gets nominated and then 2 days later I gain interest (promoted to Closer for instance).  This can't really be accounted for, so I'm just going to risk it for the sake of the league...

Thank you all for your suggestions.  They didn't work for me in this exact situation, but I learned a lot in the process and was exposed to some new interesting ideas.

I'm going to accept mgorven's answer as I feel the trusted 3rd party approach is the most correct general use case solution.  I'm not sure what the protocol is for this...

This is an interesting discussion of the problem, as well as this crypto.SE question (they seem to be called "time-lock puzzles").

The most reliable scheme is to use a trusted third party which provides a public key and only releases the private key some time later.

The only scheme that doesn't require a trusted third party is to iteratively hash a random value for the time period you want, use the result to encrypt the information, and then discard the result and store the initial random value. To decrypt the data the iterative hashing needs to be performed again in order to recover the result which was used to encrypt the data, which should take the same amount of time it did before (although hashing can be sped up with GPUs or ASICs).


Need 32-bit mixing function that has perfect avalanche between octets for my hobby tinkering project, I need a mixing function that takes 32-bit input and has 32-bit output (and will, most likely, run in a 32-bit C environment) and the following property (independent of endianness, i.e. it’s enough to only look at either big endian or little endian (or pdp endian) systems):

union u {
    uint32_t u32;
    uint8_t u8[4];
} ival, oval, ival2, oval2;
int x;

ival.u32 = /* some unsigned 32-bit value */;
oval.u32 = ƒ(ival.u32);

x = /* some value ∈ { 0, 1, 2, 3 } */;
ival2.u32 = ival.u32;
ival2.u8[x] ^= /* some nonzero octet */;
/* ival2 = ival where exactly one input octet differs */
oval2.u32 = ƒ(ival2.u32);
assert(oval2.u8[0] ≠ oval.u8[0]); /* first output octet differs */
assert(oval2.u8[1] ≠ oval.u8[1]); /* second output octet differs */
assert(oval2.u8[2] ≠ oval.u8[2]); /* third output octet differs */
assert(oval2.u8[3] ≠ oval.u8[3]); /* fourth output octet differs */

That is, I need a function where, when you change one of the octets in the input, all four octets of the output differ.

Since this is a 32-bit to 32-bit mapping, it can be a perfect mixing function (bijective, not one-way); this would be extremely beneficial because I could then replace the Final function of a 32-bit (nōn-cryptographic) hash (based on Jenkins’ one-at-a-time but tweaked) I’m using in the same context with it, too, and it would not lose any fractional bits of entropy from the input.

Of course I could do this “the simple way” with lookup tables, but the idea is to have this in only a few lines of code (that is, few machine instructions), either completely algorithmic, or with only, say, up to 256 bytes of read-only data. I bet there’s something like this already around. (My target CPUs are, for now, i486, sparc v8, 32-bit MIPS, but I’d want it in portable code, not assembly; C is just fine as long as it uses only unsigned integers, since I’ll most likely need to implement it in C.)

Please only include code snippets if they are true Public Domain (e.g. government work) or I can reuse them under the MIT Licence, the MirOS Licence, or the BSD Licence, or in a language not C with a permission for me to “rewrite the same algorithm” in C (while not copying a line of code); otherwise, please only include algorithmic descriptions that are enough for me to write C code from it. And nothing that’s legally dangerous or questionable of course ☺

My strength is coding, not mathematics (I already had to prove the bijectivity of the Finish function of my modified Jenkins-OAAT empirically, i.e. by trying all possible 2³² combinations), that’s why I thought to ask here. (No homework or commercial stuff, just trying to improve the world, in the context of the BSD Unix operating systems, and Open Source.)

At first glance, the MixColumn step from AES (actually, a single column of that transform) sounds like precisely what you're looking for.  It is invertable (AES depends on that), and it does have the property that if one input octet changes, then all four output octets are guaranteed to change.

Most commonly, it's done by table lookup; however there's no reason it couldn't be done by inline code (and that inline code ought to fit in 256 bytes).


Size of a MAC for a quickly checked message? Let suppose that we have to check a message that was written one second ago. The message is discarded immediately after having being checked. What "minimal" size for such a MAC is secure?

If the MAC is well designed and there is no better attack than guessing, the attacker can choose at least two attacks:

a. Find the key for MAC and be able to sign any message.

b. Guess (maybe randomly) a MAC of an arbitrary message. (If unsuccessful, maybe retry the attack.)

The feasibility of attack a depends on the size of the key, but not on the size of the MAC itself. (Well, smaller MAC means potentially less information leaked about the key, but this is rather a minor effect.) Small MAC thus does not increase the probability of the key being cracked.

The important point: Attacker without the key can't just bruteforce a MAC for an arbitrary message, even if the MAC length is 1 bit. Since MAC is symmetric and key is kept in secret (there is no public key), attacker with a valid pair of message and its MAC can't verify it offline.

None of these facts, however, mitigates attack b. The attack b may be a real threat with a short MAC. Feasibility of the attack will depend on details that are not available. (It, however, does not much depend on the time window between message sent and message recieved.) If the MAC does not protect anything very valuable and the attacker is likely to be traced and killed after the first unsuccessful attempt to forge a message, one bit MAC might be very sufficient. If the attacker can do many unsuccessful tries without any problem, then the MAC must be much longer in order to resist such attack. How much long? It depends on the feasible online attack rate. Plus, you are likely to want a safety margin, don't forget about that.

There is one more issue. Where would you get a MAC function that outputs a shorter MAC? When you take an obsolete MAC function, there might be some serious issues (e.g. short key). When you use an existing MAC function and shorten the output from it, it is not guaranteed to provide desired level of security. For example, a MAC function with 128b  output might provide signifficanty less enthrophy in the output due to some redundancy or probability characteristics. This should not be an issue with HMAC, which is hash-based.

I hope you question is rather theoretical one (i.e. you are curious if this is safe) and you don't wan't to implement such system. The MAC overhead should be usually negligible and there should be no serious reason for using a short MAC. The benefits of slightly smaller MACs are usually not worth of a serious reasoning about security of that system.


Digital Signature using symmetric key cryptography Generally digital signature is a public key cryptography concept.But it needs high overhead.
So is there any publication or link available where 'digital signature using symmetric key' has been explained?
Can one generate an algorithm combining the public key and private key of RSA algorithm to make it a symmetric key?

You may be interested in reading up on the The TESLA Broadcast Authentication Protocol which uses the one-way key chain concept to achieve authentication.

The basic idea of the key chain is to hash a secret key value repeatedly and use the hashes or "keys" in the reverse order for authentication. A simple example would be for Alice to compute

         H(H(H(H(secret key))))

and send this value securely to the Bob. Next, Alice disclose the value of

         H(H(H(secret key))).

Since the hash function, H(.) is assumed to be one-way then any party with knowledge of the pre-image is assumed to be Alice.

The sender uses the most recent value from the one-way chain as a cryptographic key to compute a MAC. Each receiver can verify that the disclosed key is correct (using self-authentication and previously released keys). The authors state that any key of the key chain can serve as a key chain commitment and is similar to a public key of a digital signature


Attack being kind of completely puzzled? I am reading this paper "The security of Hidden Field Equations (HFE)"

and at the end of the page 4 the author wrote:

  Thus, after all, this belief about every attack being kind of
  ”completely puzzled by the irreducible randomness of answers to all possible
  questions”, maybe it is not necessary at all to achieve security ?

I know what is irreducible randomness but sincerily I do not understand that sentence.

Could you explain me please what that sentence means?

I think the key to comprehending this passage is the first sentence of the paragraph it is in, which refers to a "random oracle paradigm". From wikipedia, a random oracle is essentially a black-box function; deterministic and repeatable, yet its output is indistinguishable from random noise. The random oracle paradigm is defining the security of a cryptographic primitive by comparing it to a random oracle, i.e. does it leak any information about its function such that its output can be distinguished from random noise. This, the paper argues, is a reasonable standard for symetric primitives, but unreasonable for asymmetric ones. The crux of their argument is, in essence, secure symmetric primitives have very complex internal function, but asymmetric primitives are comparable very simple. Thus, as the sentence you provide very unclearly states, it is unreasonable to think that an attacker would have no knowledge of the internal function of asymmetric primitives, and so it is not necessary that an asymetric primitive's output leak no information about its function, i.e. indistinguishable from random noise, for it to be secure.


How unsafe is to share parts of a password The best way to ask this question and have a concrete answer is to set a very specific example. This is the example I would be interested in reading an answer to:

Consider that my friend Alice has several (~5) hard drives encrypted with Truecrypt. Alice is using AES (256-bit, 14 rounds) with RIPEMD-160. I could see that she has a script for mounting the different drives -I guess that because she's pretty lazy and just wants to type in one password. Of course, every disk is salted differently, etcetera.

From her script, I can figure out that the password for each drive comes from concatenating a common string (for all drives) with a fixed string set in the script (different for every drive). I don't know the length of the common string (it's user typed), but the fixed strings are like 6-10 characters long.

Let's then first assume that I don't know the common part of the password, but I know the fixed part for every disk because I see it in the script.

So the question is, and don't be afraid of diving into explaining the mathematical reason- how insecure is the fact that she uses a common string, and how could I attack that flaw?

And secondly, what if I didn't know the fixed part for every hard drive but I knew that they begin with the same common part (which value is unknown too)?

If I know your password is k bits long and I know the m bits, then I have to brute force the rest of the k-m bits. That's the standard for any algorithm and independent of whether this is prefix, suffix etc. This means that I have $2^{k-m}$ tests to make.

However, you can even do better, You can say that you have a decayed version of the key, or you have partial key exposure, you have some plaintexts and the according ciphertexts. In this scenario, there are several effective attacks, even for AES, with different approaches, even SAT solvers. Have a look at the following papers:

Halderman, J. Alex, et al. "Lest we remember: cold-boot attacks on encryption keys." Communications of the ACM 52.5 (2009): 91-98.
Kamal, Abdel Alim, and Amr M. Youssef. "Applications of SAT solvers to AES key recovery from decayed key schedule images." Emerging Security Information Systems and Technologies (SECURWARE), 2010 Fourth International Conference on. IEEE, 2010.
Liao, Xiaojuan, et al. "Using MaxSAT to Correct Errors in AES Key Schedule Images." Tools with Artificial Intelligence (ICTAI), 2013 IEEE 25th International Conference on. IEEE, 2013.

Of course there are limitations as you can see from the papers, but depending on how much bits you want to crack, it might be easier to go this way than brute force them.


Are there any real protocols secure in the random oracle model that have been broken in practice? Has any protocol ever been proven secure in the random oracle model and then broken in practice, despite the use of a good hash function in the actual implementation?

The one real example out there is RMAC. This was proposed in this NIST standard, and was shown to be broken for some instantiations in practice in the paper Analysis of RMAC by Knudsen and Kohno. The construction is proven secure in the random-oracle model in the paper: On the Security of Randomized CBC–MAC Beyond the Birthday Paradox Limit: A New Construction from FSE 2002. (Although, when instantiating with a block cipher it's more like the ideal cipher model.)

Another, less convincing example is to generate a MAC by compute $SHA(K\|M)$ which is vulnerable to extension attacks, but is secure in the random-oracle model. This is less convincing since most people knew that this was vulnerable to extension attacks.


Restore AES key from MPC I know there are many AES MPC implementations, but in general, is it possible to restore the raw AES key if we have access to all of the nodes? If we take, for example, VIFF and its "shares". Is it difficult?

If you have the values of all nodes you can always easily recover the plaintext in MPC.


How can process algebra help to design security protocols? Would you please tell me how process algebra could help me to design security protocols?

More specifically, can I use it for proving the security of protocols?

Is process algebra used for any security protocol or specific types of protocol such as network protocols?

More specifically, can I use it for proving the security of protocols?

Sort-of.
Using process algebras you can model or describe your protocol using a language that has a formally defined syntax and semantic (= meaning) just like you can describe a protocol using code or text. The advantage of process algebras is that the formal syntax and semantics can be used by tools to do one of the following:

Find a counter-example to a claimed property.
Prove that the protocol satisfies a claimed property (not always possible).
Reduce the proof of the complete protocol to some more easily manually achieved proofs.


Hardness of EC-based DLP I have a question about EC-based DLP. I know that getting $k$ is hard when $kG$ is known. ($G$ is a generator)
Question:
Is it still hard getting $kG$ where $x$ is known? (in here, $kG=(x,y)$)
or getting $k$ where $x$ is known?
I think the former is not computationally hard. Am I right?

For a given x there are only two possible y coordinates figuring that out is just a matter of solving the curve equation for y.

Afterwards  you just end up with a regular DLOG problem which is hard (if your x is for a point with large enough order order your curve order is prime).


Elliptic curve trapdoor function without modular arithmetic? From what I understand, an elliptic contains a set points satisfying the equation

$y^2=x^3 + ax + b$

together with the point at infity.

It seems clear how multiplication with a scalar and a point works, and how point addition works. Discussions about cryptographic applications usually jump right to curves defined over finite fields at this point. I think I understand how that works as well.

What doesn't make sense is whether a curve defined over the field of real numbers could also work as a trapdoor.

If I know that point Q results from multiplication of some integer with the generator point on a curve over real numbers

$Q = dG$

what feasible methods exist to compute d given only a, b, and Q, and G?

In other words, aside from convenience in implementation, what exactly does the finite field add to elliptic curves as trapdoors?

I've seen this discussion, but it doesn't seem to directly address the question here.

First, as poncho correctly noted in a comment, real-based values don't work well with computers, because they require an infinite series / sequence representation and handling infinite amounts of data with a finite amount of storage usually doesn't end well, especially if you don't want to give away structure like in this case.

Second, picking keys is hard if you consider infinite ranges (even if there's an infinite amount of numbers between any two numbers), because you can't sample from an infinite set uniformly at random (then every element would have probability 0 of being picked).

Third, real-numbers often allow for more structure than we'd like. Take for example the logarithm. Computing $\log_3 b$ is easy in $\mathbb R$ (we know efficient algorithms that will yield a solid approximation) whereas finding this over $\mathbb Z_p$ tends to be hard. The fear is that a similar property can be found for the elliptic curve discrete logarithm problem. Also most problems over $\mathbb R$ are a matter of finding a good enough approximation where you can use intermediate approximations and have helpful navigatory metrics and thelike, whereas with crypto you want "hit-or-miss" and no guidance in the right direction.


Show that CPA-security implies security against plaintext recovery Consider the following experiment:

$k = Gen(1^n)$
$m \stackrel{u}{\in} \{0,1\}^{l(n)}$
$c = Enc_k(m)$
$m' = B(1^n,c)$

Define the winning event as $m' = m$. I would like to show that if the encryption scheme $Enc$ is CPA-secure thn every PPT-algorithm $B$ can only succeed with negligible probability in the above experiment.

Proposal

This is the solution I have come up myself with:

Your solution is almost correct. Just don't forget to consider the following two cases: 1) $m_0$ and $m_1$ may be the same, then $A$ will have to guess the secret bit $b$ blindly; 2) $B$ may return the other message, e.g., $B$ happens to return $m_1$ when given $E_k(m_0)$, then $A$'s output will be wrong. Note that 1) and 2) occur with only negligible probabilities.


Padding always the same, problem or not? I need to transmit long encrypted messages to a smartcard over a limited capacity link so I need to fragment the messages somewhere before sending thzm.

My problem is that I split the message into 64-byte blocks and then apply a pkcs7 padding. The result is that the padded message always ends with a full block of 16s before encryption. Does this pose a security problem since an attacker will know the last plaintext block ?

One possible solution I might use is splitting into blocks of size 64+x instaed with x random between 0 and 15 so the padding will not be predictable. Is this a good/better idea ?

PS: I use AES-CBC with 128 bit keys

No, it is not a problem to have the same padding at the end of a message. Some known plaintext is often available in practice (protocol fields, etc). The security of the system is (or at least should be) based entirely on the key.

If you are really worried about it for some reason just change the IV for each 64-byte block. Or as CodesInChaos said in a comment, if messages are always a multiple of 16 bytes, don't even use padding.


Difference between linear cryptanalysis and differential cryptanalysis What is the main difference between linear cryptanalysis and differential cryptanalysis? For example in relation to DES?

Differential cryptanalysis works on differences. Linear cryptanalysis works on linearity. Neat, isn't it ?

Instead of speaking of how they differ, it is easier to list their common features. Both kinds of attacks:

Use a lot of known pairs plaintext/ciphertext (many input messages encrypted with the same key, and, for each of them, the attacker knows both the block value before encryption, and after).
Rely on an "approximation" of the internal behaviour of the encryption function, which holds with a small but non-zero probability for some input.
Work with detected weaknesses in the internal structure of the algorithm; they don't work "generically".

With differential cryptanalysis, the known plaintext/ciphertext pairs must be organized in pairs where both plaintexts differ by a specific difference ("difference" being a XOR, a subtraction... whatever works well algebraically with the algorithm at hand; for DES, this is XOR). The "approximation" is that this input difference will yield another specific difference on the output with a probability which is somewhat higher than what could be obtained with pure randomness, and the exact difference which will most probably appear depends on some of the key bits. Successful differential cryptanalysis normally requires chosen plaintext/ciphertext pairs (the attacker gets to choose the plaintexts or the ciphertexts).

With linear cryptanalysis, the approximation is a linear formula (i.e. a bunch of XOR on bits) which links together some input bits, some output bits and some key bits, with a probability somewhat higher than what could be obtained with pure random. This "linear formula" works best (i.e. is fulfilled most often) when the hypothesis on the involved key bits is correct, so the analysis yields a few key bits.

The most salient difference between linear and differential cryptanalysis is the known/chosen plaintext duality. For linear cryptanalysis, known random plaintexts are sufficient, but differential cryptanalysis requires chosen plaintexts, which, depending on the context, may or may not be a significant problem for the attacker.

Linear cryptanalysis is easier to grasp, so begin with that one. This PhD thesis is a nice introduction. For differential cryptanalysis, read this well-explained article.


Why not use ordinary hash functions for password hashing? Assume we have a password and add a unique salt to prevent various precomputation attacks.

Why don't we do this:

SHA256(SHA256(SHA256 ...(Password || Salt)))

So, we have n iterations (like in PBKDF2) and because of the iterations, it should take much longer to compute the hash for a password, which is key stretching.

Can someone explain to a newbie like me why we don't use specific algorithms like scrypt, PBKDF2, or Argon2 and do this?

What's proposed, and PBKDF2 alike, give significantly less protection than scrypt or Argon2. That's because adversaries trying many passwords on parallel hardware can do so at lesser cost, for a given time or CPU × time on the legitimate user's side. With scrypt or Argon2, but not the question's construct or PBKDF2:

A significant amount of memory is required to compute the function. This implies that the adversary has to invest in that memory for each instance of password searcher, and can't use GPUs efficiently. Password cracking for PBKDF2 (or worse) entropy stretching is common practice, using GPUS, FPGAs, I guess ASICs. I conjecture government agencies do this routinely. Bitcoin mining ASICs are close to being usable to attack the question's construct at high rate (but are not AFAIK), and PBKDF2 has comparable complexity.
Multiple CPUs on the legitimate user's side are leveraged. This allows to perform more work on the legitimate side for a given user's wait (raising attack cost correspondingly). That's useful when the limiting factor for parametrization of the effort per password is the user's waiting time.

The question's construct is close to PBKDF1 and comparable to PBKDF2. The main operational differences are that

PBKDF1 and PBKDF2 have variable size output; PBKDF1 has built-in truncation, and PBKDF2 additionally allows large output. That makes them usable in more situations. But large output is immaterial for password storage, and PBKDF2's way of generating large output is poor, as noted by CodesInChaos in comment.
The question's construct (and PBKDF1) has the dubious property that for all $\mathsf{password}$, $\mathsf{salt}$, and bytestring $b$, it holds $F(\mathsf{password}\mathbin\|b,\mathsf{salt})=F(\mathsf{password},b\mathbin\|\mathsf{salt})$, which PBKDF2 avoids. This is typically immaterial for password storage, but conceivably could be an issue in some other uses of PBKDF2. However PBKDF2 used with HMAC (as it almost always is) has another potentially undesirable regularity, as noted in said comment: a long $\mathsf{password}$ and its hash are equivalent.
For 1 iteration of SHA-256 and uniform random input, the (likely) entropy in the output is only about $256-0.827\dots$ bit (see this), and that keeps on decreasing as the number of iterations grows (see this and this). That contrasts with PBKDF2-HMAC-SHA-256 for 256-bit output (probably) next to fully and uniformly covering it's output space, with no marked decrease as the number of rounds increases, for near 256-bit entropy. However that effect in the question's construct and PBKDF1 remains beyond experimentally observable as far as we know (that would imply an attack on SHA-256), nearly disappears anyway for significantly truncated output, and has no practical significance.


why a group used in cipher based on DLP must be Abelian group? I can't understand it because $(g^x)^y=(g^y)^x$ in nonabelian group too.

thank you very much for read my question

What you are asking is in some sense a tautology. In any group $G$, Abelian or not, the subgroup generated by an element $g \in G$ is Abelian. (Recall: the subgroup generated by $g$ is:
$
\langle g\rangle := \{g^0, g^1, g^2....\}
$
).

Hence, you can probably take your favourite DLP-based encryption scheme and implement it in $G$, without dealing with the fact that it is not Abelian. Indeed, the only fact you need is the existence of a subgroup $G_1$ with large prime order $p$.

For example, consider a large prime $p$ and the corresponding  Dihedral group $D_p$. It is one of the simplest examples for a non-Abelian group, and it has a subgroup of order $p$. Let $g$ be random element of order $p$ (that is easy to verify, since elements in $D_p$ are either of order $p$ or 2). Now, you define El-Gamal encryption as usual:

Secret key is $x \in \mathbb{Z}_p^*$ to your choice, public key is $(D_p, p, g, h = g^x)$. We encrypt a message $m \in D_p$ by choosing a random $y\in \mathbb{Z}_p^*$ and computing
$$
m \mapsto (c_1, c_2) = (g^y, m \cdot h^y),
$$
and decrypt by computing
$$
(c_1, c_2) \mapsto c_2 \cdot c_1^{-x}.
$$

Note that in an Abelian group, we could also decrypt by multiplying in a different order:
$$
(c_1, c_2) \mapsto  c_1^{-x} \cdot c_2,
$$
but, well, who cares - just remember to multiply in the right order.

An interesting question in my opinion, is what can be gained by considering an underlying group that is not Abelian. Indeed, if the presentation of the group if complicated, perhaps DLP is harder. This is the case with elliptic curve based cryptography: the groups considered are cyclic as usual, but the presentation of the group is far more complicated than $\mathbb{Z}_p$, leading to better security against DLP.


Intuition behind the asymmetry between invertibility of key and ciphertext in block ciphers I have studied the design of block ciphers like DES and AES.

I know the actual algorithms, but I don't intuitively "grok" the most important property of them:

The most important property, is that if you have the key and the ciphertext, you can calculate easily the plaintext, but if you have the plaintext and ciphertext, you cannot easily calculate the key.

That is, the block cipher is a function $$f(P,K)= C$$ and the essential property is that the inverse w.r.t. P is very easily caclulated, but the inverse w.r.t. K is not.

I don't intuitively understand why this assymmetry is true, even though I know how to actually do the decryption algorithm. Is there an intuitive explanation of this asymmetry?

If you had a block cipher with this property, it would necessarily be insecure!

The most basic requirement for a block cipher is to be a pseudorandom function (PRF). In the game that defines security of PRFs, the attacker gets to choose input blocks $x_1, x_2, \ldots$ and gets back responses $y_1, y_2, \ldots$. It should be hard to distinguish whether the $y_i$'s are uniformly random or have the form $y_i = F(k,x_i)$ for a random (secret) key $k$.

Suppose your block cipher was ``key-invertible'' in the way you describe. Here's an attack against the PRF security of the block cipher. Ask for some $x_1$ and get back $y_1$. Now you do this key inversion process and you can learn (a candidate) key $k'$. Then you can make one more query on $x_2$ and get back $y_2$. If $y_2 = F(k',x_2)$ then you guess that you are getting outputs of the PRF; otherwise you guess that you are getting random responses.

This attack completely breaks PRF security. It assumes that the key-inversion process is perfectly correct --- that is, given $x$ and $y = F(k,x)$ for unknown $k$, you can always compute that exact $k$. Even if you assume the key-inversion procedure is not always correct (e.g., maybe there are two keys that satisfy $F(k,x) = F(k',x)$ so sometimes you get it wrong), It seems likely to me that this attack can be extended.


XSalsa20 + Poly1305 authentication wtihout tag Do I understand correctly that XSalsa20 + Poly1305 provides authentication without a tag? If so, then how does that work?
I came to that conclusion by reading http://nacl.cr.yp.to/secretbox.html, "Secret-key authenticated encryption", where it states (as far as I understand) that the ciphertext has the same length as the plaintext.

The documentation is a bit misleading about crypto_secretbox_xsalsa20poly1305 that uses a 16-byte authentication tag of poly1305. The libsodium has more clear explanation on it. From Bernstein' paper's abstract;

Poly1305-AES computes a 16-byte authenticator of a variable-length message, using a 16-byte AES key, a 16-byte additional key, and a 16-byte nonce

I would be surprised that one authenticates an arbitrary message without using a MAC tag (Wikipedia quote);

In cryptography, a message authentication code (MAC), sometimes known as a tag, is a short piece of information used to authenticate a message—in other words, to confirm that the message came from the stated sender (its authenticity) and has not been changed.

Therefore the short piece of information must be somewhere!.


Is "6 bit packed ASCII" an effective encoding to obscure text data? I wrote a routine for a former employer that took the low six bits of ASCII text and "compressed" by cramming the bits together, so that 4 bytes reduced to 3. This had the advantage of automatically folding lowercase to uppercase (not reversibly) with no computational effort. (Our text data was supposed to be just upper case letters, digits and punctuation. Can you say COBOL? I knew you could.) Note that I also ignored the first 32 ASCII characters as well. (They did not appear in the input data.)

Would this encoding method obfuscate text (where SHOUTING was acceptable) in a way that does not yield readily to simple analysis? The data would be encoded from 4 bytes down to 3 like this - (assume that we are only looking at the low 6 bits of every byte, the high 2 bits are just clipped off):

B1 = all 6 bits of first byte + low 2 bits of 2nd byte
B2 = "upper" 4 bits of 2nd byte + lower 4 bits of 3rd byte
B3 = last 2 bits of 3rd byte + all 6 bits of 4th byte

(Is there a prettier picture to illustrate this?)

No. I actually new how to do such coding on my MSX machine in the mid-eighties (when I was 12). I'm pretty sure I could have decoded it back then. Note that binary code was much more used at that time; you had to code in assembler to get any kind of performance. It was also pretty common to compress things in such a way because you did not have much memory either.

What you're describing is an encoding scheme. Encoding is something different from encryption. Obviously it can obfuscate text, but that obfuscation is just skin deep. This is especially the case if somebody starts to look for strings.

You could however encode to base64 with a different alphabet. That kind of obfuscate things enough that you have to revert the encoding to read it. You could also XOR your scheme with a (multi-)byte pattern to make things less readable for humans.


Prevent hash collisions with HMAC secret as IV Our organistation would like to hash large file paths to asssign to a specific object. To prevent hash collisions, I thought we can use the same sort of technique as we use to prevent rainbow tables in password hashes. When you hash the value 'sample data' we will first prepend an IV, which will be used as hmac secret to verify the hash.

function makeHash($data,$algo='sha256',$ivKey=null) {
  if(empty($ivKey)) {
 $ivKey = openssl_random_pseudo_bytes(16);
  }

    $result = $ivKey.hash_hmac($algo,$data,$ivKey,true);
 return base64_encode($result);
}

function verifyHash($data,$hash,$algo='sha256') {

  $result = base64_decode($hash);
   $ivKey =  mb_substr($result,0,16,'8bit');
   $dataHash = makeHash($data,$algo,$ivKey);

  return $hash == $dataHash;
}

Usage example:

$hash = makeHash('sample data');
echo $hash;
var_dump(verifyHash('sample data',$hash));
/**
Output:
 I9Kl9Mkq/6ee3xQixrDn3YImRAywz0rhmBBxRjrfRWiGeRuBrIkREirgKBDr8Gzh
 bool(true)
*/

Would this be a good way to prevent collisions?

Probably not, unless the paths you are trying to protect include a secret large enough to make it impossible to brute force the hash.

The problem is that this will protect against people finding paths by matching against all the possible values. But assuming the paths can be easily guessed, it is probably not enough to prevent brute-forcing a single path at a time. Furthermore, if you have a hierarchic tree and you also hash the roots of a particular branch, then you can first brute force the root, then the first subdirectory ... until you reach the desired end node.

Most of the time people will protect URL's by keeping a map, where a random value of about 64 to 128 bits is mapped to a specific URL (or path). Obviously the map itself must then be kept secure.

You can slightly approve your algorithm by actually using PBKDF2 with a high iteration count. But even with that brute-forcing the path could be doable.


Euler's totient function and Carmichael's totient function in RSA I'm a high school student taking IB and I'm doing my EE on Maths, more specifically on the effectiveness of Euler's totient function and Carmichael's totient function in RSA.

Am I right in thinking that Euler's and Carmichael's can be used interchangeably to generate the public key in RSA?
To compare their 'effectiveness' I will first compare the amount of time it takes to generate a public key using each function based on time complexity. Secondly, I want to compare the security of the public key (meaning 'how difficult it is to guess the private key given the public key'). But how? Is there an algorithm to use to test the security of an encryption key?

Many thanks!

Am I right in thinking that Euler's and Carmichael's can be used interchangeably to generate the public key in RSA?

Yes.  The requirement is that the public exponent $e$ have an inverse modulo $\phi(n)$ or $\lambda(n)$, whichever you use—and the two numbers share prime factorization, differing only in multiplicity, so $e$ is coprime with $\phi(n)$ iff $e$ is coprime with $\lambda(n)$.

  To compare their 'effectiveness' I will first compare the amount of time it takes to generate a public key using each function based on time complexity. Secondly, I want to compare the security of the public key (meaning 'how difficult it is to guess the private key given the public key'). But how? Is there an algorithm to use to test the security of an encryption key?

There is no algorithm to test the security of a particular key.  There is literature on the security of systems for generating keys, though—and for RSA keys there are many such systems[1], with some pitfalls if you're not careful about using the fancy ones[2].

However, this is all about generation of the prime factors.  The public exponent $e$ should be a fixed constant like 3 or 65537; then the private exponent $d$ solves either $e\cdot d \equiv 1 \pmod{\phi(n)}$ or $e\cdot d \equiv 1 \pmod{\lambda(n)}$.  If you use $\phi(n)$, $d$ might be larger, so the private key operation costs more to do the same thing.  That is, the only difference the choice of $\phi(n)$ vs. $\lambda(n)$ makes is efficiency of the private key operation.


Why did NIST remove The Lempel-Ziv Compression test from the Statistical Test Suite? NIST removed "The Lempel-Ziv Compression" test from the Statistical Test Suite in revision 2008 and above and has not incorporated it since – see revision 2010.

Why was it removed? Does it no longer provide sufficient testing of a PRNG or was it simply superseded by better tests?

According to the paper On Lempel-Ziv Complexity of Sequences by Doganaksoy and Gologlu,

  A test based on Lempel-Ziv complexity was used in the NIST test suite, to test the randomness of sequences. However the test had some weaknesses. First of all, the test could only be applied to data of a specified length: $10^6$ bits. Moreover, the test used empirical data generated by SHA-1 (under randomness assumptions) for estimating the expected value of Lempel-Ziv complexity of sequences of length $10^6$ bits. Apparently, the data generated by SHA-1 led to not-so-good an estimate, hence, for instance, first $10^6$ bits of the binary expansion of $e$ failed the randomness test. Using asymptotic formulae for an estimate will not work either, since the sequences, as we will see in the forthcoming sections, are distributed tightly around the mean. Recently, apparently because of the spelt out reasons, Lempel-Ziv test had been excluded from the NIST test suite.

The Crypt-XS package, part of the NIST suite, includes the simply named sequence complexity test, which is based on Lempel-Ziv compression.


Is There any Risk to Using Meaningful Text as One Time Pad Key? Let's say two people have the same edition of the same magazine. The knowledge that the magazine will be used as a one time pad is secret.

Is there any risk to using this as opposed to randomly generated numbers?

It does not seem to me that any additional risk is introduced, besides running a brute force with real phrases from common books, but that could also lead to a number of inaccurate "descriptions".

So, then, from a cryptographic perspective, are "real sentences" less secure?

There are two major risks, one of which is very difficult to quantify. So let's start with that.

Kerckhoffs' principle states that you have to assume that only a key is secret, not the means of communication.   There's you and your friend, lover or co-conspirator and you communicate. The state knows this, and a search of your properties reveals a OTP was used, generated from some magazine. Assume you read a lot so you have many mags, say 10,000 as you have a rather large bookshelf.  Guessing the correct one is only equivalent to guessing a ~13 bit key. That's not a lot.  Granted you then have to work out which parts of the magazine were used, but you can see that the state is closing in on you.  There are other pragmatic issues to quantifying this like eating the magazine afterwards, but still... Compare that to an electro-mechanically generated key of the length of a Twitter message.  That's 1280 bits, which is oodles better.

Another risk is that the entropy rate of the key material must >= entropy rate of the plain text.  This is the fundamental requirement for a OTP to preserve perfect secrecy.  If your magazine is about fishing or football, the entropy rate of the text will be quite low, say just ~2-3 bits/character. An article by Umberto Eco will fare better, but not by much.  Your secret message will have to have a correspondingly low entropy rate.  So if you were to try and encrypt binary data approaching 8 bits/byte, perfect secrecy is impossible.  Your message would be capable of being easily brute forced. You can mitigate this by using randomness extraction on the magazine text to condense the entropy to 8 bits/character. That still leaves my first and main risk though.

This is one of the fallacies about using such key material, and it's perfectly understandable given human senses.  You think that finding the exact magazine is so hard it borders on impossible.  It's only 13 bits improbable, whilst to us 10,000 magazines seems a lot. Compared to truly random keys, it's no security at all.


Secret sharing where the combination of shares matters In Shamir's secret sharing scheme, any combination of shares (that pass the threshold) will result in the secret being revealed. Is it possible to have a system where some combinations are invalid?

For example, imagine a company's trade secret is split into 10 shares with a threshold of 3. You give 3 to the CEO, 2 to each executive (of which there are 2), and the remaining 3 shares go out to 3 secretaries. This has this effect.

CEO(3)                      = 3 -> Secret recovered
Exec(2) + Exec(2)           = 4 -> Secret recovered
Exec(2)                     = 2 -> Secret NOT recovered
Secr(1) + Secr(1)           = 2 -> Secret NOT recovered
Secr(1) + Secr(1) + Secr(1) = 3 -> Secret recovered

It also allows for this case.

Exec(2) + Secr(1) = 3 -> Secret recovered

In this case, an executive needs only to consult a secretary before unlocking the trade secret.

Is it possible to have a scheme where an executive's shares and a secretary's share cannot be combined?

I can think of ways to extend Shamir's scheme to have this behavior in this example. For instance, using two instances of the Shamir scheme to make the executives' shares and the secretarys' shares be incompatible. This has the problem that you need to maintain two copies of the same secret. I'm looking for a better solution.

Yes. It is possible to construct secret sharing schemes for general (monotone) access structures. You can read about the first construction in the paper called Secret Sharing Scheme Realizing General Access Structure. I also suggest reading this survey by Amos Beimel.


Why does nobody use (or break) the Camellia Cipher? If Camellia is of equivalent security and speed to AES, concerns arise.

First of all, assuming the above, why is Camellia so rarely used in practice?
Why aren't there any breaks in Camellia? Does that mean that Camellia is currently more secure than AES, or is this a result of the lack of research on the cryptanalysis of the cipher?

There are a variety of reasons why AES is more widely used:

AES is a standard.
AES has been vetted by cryptanalysts more extensively than Camellia.  As a result, we can have greater confidence in the security of AES than in Camellia.  Therefore, on the merits, there may be good reasons to choose AES over Camellia.
AES is a government standard (FIPS).  Government procurements may be required to comply with applicable government standards.  Therefore, when selling to the government, AES may be required; if so, Camellia isn't an acceptable substitute.
AES is a industry standard.  No one will get fired for using AES. If (say) Apple uses AES, and AES gets broken, the newspaper headline won't be about Apple; it'll be about flaws in something everyone is using. On the other hand, if Apple uses Camellia and Camellia gets broken, the newspaper headline will be about why Apple took it upon themselves to deviate from industry standard practice and how that led to a security breach in their systems.  Therefore, aside from its merits, there's an incentive to choose the industry standard.
Camellia is patented.  AES is unpatented and free for all to use, without patent encumbrances.  Regardless of what licenses might be available, many people are a bit wary about any patented algorithm, due to uncertainty, IP risks, etc.  If the unencumbered version is every bit as good, it's easier to use the unencumbered version.  Also, it is possible that some open source crypto library developers may be less likely to implement Camellia, because of the potential patent situation or because of the reduced demand to the above factors, so standard crypto libraries are less likely to Camellia.  Similarly, many standards bodies have a bias against patent-encumbered algorithms, when there are alternatives that are every bit as good; therefore, some standards bodies may be less likely to use Camellia when they standardize on network protocols that require crypto.
AES is entrenched.  AES is a brand name that is widely known and recognized.  Also, AES is good enough.  Camellia is newer, and the benefits of Camellia are unclear or not as well known.  (In many contexts, Camellia has no obvious advantages, so a developer might not see any reason to adopt it instead of AES, if they already know and trust AES and consider AES adequate for their needs.)  There's no shortage of other block ciphers out there that could be considered, but if AES is good enough, there's not much incentive to use them.


What is Phase space reconstruction attack on chaotic encryption algorithm? What exactly does it mean? How can someone attack an algo using phase space reconstruction?
I have been searching the internet for more than 3 days and cannot find anything close to explaining this topic.

In cryptography, "phase space reconstruction attack" seems used only in the field of cryptography based on chaotic systems, which itself is too often happy with vague arguments and definitions where math is due. Accordingly, this field is markedly underrepresented in cryptographic publications with a peer-review system that I trust.

We are told by the OP in comment:

  I am working on final year project where I am trying to improve the algorithm Image encryption using chaotic logistic map. Therefore I have no other option. I have to check whether my improvements can deter this attack or not.

Multiple alarm bells are ringing.

This article was published in Image and Vision Computing, a journal with "primary aim the provision of an effective medium of interchange for the results of high quality theoretical and applied research fundamental to all aspects of image interpretation and computer vision". That is, not cryptography.

Further, the article makes a most basic, serious, and common error in cryptography based on chaotic systems: it fails to consider the issue of number representation, numerical precision, and rounding, when it defines the iteration studied as:
$$\begin{align}X_{n+1}&=3.9999\,X_n(1-X_n)\\
Y_{n+1}&=3.9999\,Y_n(1-Y_n)\end{align}$$
The (same) iterator used for $X$ and $Y$ is the well-studied logistic map. It is indeed chaotic, thus small errors due to the approximate representation of real numbers using floating point matter immensely: even the approximate value after a few iterations depends non only on the starting point, but on which of internal format (there has been many) is used for number representation, and rounding rules. Results (including ciphertext, and difficulty of cryptanalysis) depend heavily on if computations are done with this or that spreadsheet, programming language, compiler, options...

The OP appears locked into a final year project starting from work easily identifiable (by one with a sound scientific background) as not proper cryptography.

Addition towards actually answering the question: the iterated $X$ and $Y$ have independent state variables, and are bound to become periodic (because there are finely many values for a state in whatever computer implementation is considered). Their period depends on floating point details, and can be quite small for some choices of parameters and starting value.

It follows that each of $X$ and $Y$ will ultimately (and in practice often quickly) be in a certain (but only indirectly observable) phase in its final cycle. I vaguely get that a phase space reconstruction attack tries finding the two phases, or some fixed relation between these. Such attacks might use that the cycle lengths often share a large GCD, or can even be equal; this is made plausible by the fact that the same iterator is used for independent $X$ and $Y$.


messages to break hash modulus 2^n Let $H_{2^n}(k,m)$ be a hash function where $k$ and $n$ are unknown and $m$ is a message in the format $(m[0], m[1], ..., m[s])$, with $m[i] < 2^n$ for all $0 < i \le s$. Define the hash as:

$H_{2^n}(k,m) = (k^s + m[1]k^{s -1}+\dots + m[s -1]k + m[s]) \;mod\;2^n$

The attacker sends a set $M = \{m_1, m_2, ..., m_a\}$ of messages and wins the game if $H_{2^n}(k,m_i) = H_{2^n}(k,m_j)$ for some $m_i,m_j \in M$ where $m_i \ne m_j$.

How can the attacker choose a set $M$ that will surely win the game?

I'm guessing there must be some trick with the last part of the message (i.e. $m[s]$), for example, if the attacker sends a set $M$ where $m_i = (0,0,\dots, 1 + 2^i)$, it's possible to ignore $k^s$ and if $M$ is big enough, than its elements will collide for sure, but I don't think this is the right way to use the argument.

If k is even

Choose a string m
Choose any block of m other than the last
Flip the most signficant bit of that block.

They collide because you effictively shift all bits of that block one place to the left. If $x \equiv y \mod 2^{n-1}$ then $2x \equiv 2y \mod 2^n$.

Additionally if $k$ is even all strings with their last $n$ blocks equal collide. This is because the previous blocks have a coefficient congruent to 0 mod $2^n$. (They're multiplied by a multiple of $2^n$.)


Error propagation in CBC mode Going through the wiki for modes of operation I see that the section error propagation says that an error in one block in the ciphertext in CBC mode only impacts two blocks. I do not quite get that. If the second plaintext block is decrypted wrong, then why would it not impact the third block?

In CBC mode the decryption equation is $P_i = D_k(C_i) \oplus C_{i-1}$. If you received a corrupted $C_i$, $P_i$ and $P_{i+1}$ will be decrypted wrong, but $P_{i+2}$ no longer depends on $C_i$ and will be correct.


Largest number that could be factored in milli seconds Considering a home pc/laptop as machine used (Say typical 2.4 GHz, 16GB RAM, 4 core processor) for running any factorization algorithm. What would be the largest number that could be factored into its prime factors in milli seconds ? rather how many digits such number might have ?

We need a little bit of clarification or state some reasonable assumptions.  For instance, 2^n can be factored very quickly for ludicrously large values of n.  I assume that's not what you're asking.  You're also probably not looking for a rigorous worst case, as that depends on the algorithms and implementations.  Perhaps time taken for non-trivial random inputs.

"This can be yours for only pennies a day*"   (*: approximately 64,000).  By milliseconds, I'm assuming you mean something in the range 1-999.

On my computer, using Pari/GP or Perl/ntheory, looking at average time, 20 digit semiprimes take about 1ms, random input about 1/3 of that.  Random input is about 10ms at 31 digits, semiprimes at 26-27 digits.  Random input is about 100ms at 51 digits, semiprimes at about 38-39 digits.  Random input hits 1000ms at ~60 digits.

Those programs are handy, but certainly not state of the art for factoring.  Among other things, they only use 1 core.  Something like yafu would probably be a better benchmark, as its SIQS is extremely fast and uses multiple cores.  Last time I checked, the QS/NFS crossover was in the 100-110 digit range, and well over 1000 milliseconds.

As for algorithm, after simple things like trial division and maybe even a tiny bit of Rho/Brent, we're probably looking at ECM or QS.  P-1 may be in there as well.  SQUFOF is very nice for 64-bit inputs, but that's sub-millisecond timing for good implementations, and it doesn't work so well for larger inputs.

This is pretty old, but back in 2009 I did some tests on various factoring code.  On page 18 of this presentation it shows the number of digits possible for factoring semiprimes in 1 second to be 55 digits with yafu.  That was a Q6600, and yafu's latest code might be faster as well.


What are the time considerations with regard to security against birthday attack? When designing security for a physical safe, one of the critical specifications is how long will the safe resist attack, this tells you how quickly you must detect and respond to an attack on the safe.

As I understand it for hash functions about 80 bits is considered minimally secure, in considering the number of bits for a hash to thwart a birthday attack is there a time consideration as well?

When designing security for a physical safe, one of the critical specifications is how long will the safe resist attack, this tells you how quickly you must detect and respond to an attack on the safe.

Yes, however there's a key difference between physical safes and cryptography.  With a physical safe, the attackers must be present on site (if they could drag the safe off to their own lair, then any safe can be defeated eventually).  This physical presence is what allow the defenders to detect and respond.

Cryptography isn't necessarily like that; it may be that the attacker (for example) intercepts a packet flowing over the internet, and we have no clue that he has done so.  He can then spend as much resources as his budget allows, and we have no idea that he is doing so.  Hence, cryptography is scaled to resist attacks for an extended period of time (at least, until we don't care about whatever it was that the cryptography was protecting).

  As I understand it for hash functions about 80 bits is considered minimally secure

Actually, if the hash function needs to resist a collision attack, 80 bits are quite insufficient for anything above "kid-sister-proof".  An $n$-bit hash function can be attacked with a birthday attack with about $2^{n/2}$ hash operations; a single PC core might be able to do this many hashes in a week.

Unless there's a strong reason not to, we typically use hashes that are at least 256 bits in length (yes, SHA-1 is shorter; it's also being phased out).  This implies that a birthday attack would require around $2^{128}$ hashes; we are fairly confident that no plausible adversary can do this.

  is there a time consideration as well?

Yes, the $2^{128}$ hash evaluations is time...


How to prove element equality in G1 using Groth-Sahai proofs In the BeleniosRF e-voting scheme, Groth-Sahai proofs with the "Instantiation based on the SXDH assumption" are used (see https://eprint.iacr.org/2007/155, version 20160411:065033, page 24).

In the BeleniosRF paper on page 8, Figure 2, a Groth-Sahai proof is used to prove $g_1^\overline{r} = c_1$ with $g_1$ being the generator of the first group of a pairing. Using the notation of the Groth-Sahai paper, an equality of two elements in $A_1 = G_1$ must be proven. How can this be done?

This is most likely a special case of one of the described equation types

pairing product equation
multi-scalar equation in $G_1$
multi-scalar equation in $G_2$
quadratic equation

but I'm not seeing how it fits into one of those.

First of all, the idea of proving element equality does not make much sense, since that would reveal the secret element. $prove(X == T)$ with secret $X \in G_1$ and public constant $T \in G_1$ reveals the value of $X$. What I was looking for instead is $prove(g_1^x == T)$ with public constants $g_1, T \in G_1$ and secret scalar $x$.

It tuned out that type 2. multi-scalar equation in $G_1$ was what I was looking for. Since both left hand side and right hand side of those equations are elements in $G_1$, this is exactly what I needed. The special case to use was the liniear equation:

$A^y = T_1$

with public constants $A, T_1 \in G_1$ and private scalar $y$.

Note: Here I used the multiplicative notation for the operation in $G_1$ as it is done in the BeleniosRF paper; the GS paper uses the additive notation.


RSA-CCA security of $m || H(m)$ as input to modular exponentiation If we encrypt a message $m$ as $m || H(m)$ using textbook RSA encryption algorithm, $H$ is random oracle modeled. In this case the message can be recovered.

Is this encryption CCA secure? If so how can we prove it or not?

CCA security assumes CPA security, and $m || H(m)$ is not CPA secure. This is simple to show: say that $C = E(m || H(m))$ is known, then an adversary can simply guess $m'$ and encrypt that. Then $C' = C$ will show the adversary that $m'=m$.

To show a CCA attack you can use this attack. You can of course replace the value $2$ in that question with $y$ where $y = x || H(x)$ for any $x$. In that case you end up with $z \cdot m || H(m)$ after decryption. Calculating $m || H(m)$ will then just consist of division with $z$.

To avoid this it is of vital important that the signature is over data protected by randomized padding, and that this randomization is well distributed over the input to the RSA exponentiation. This is what OAEP does with the MGF(1) padding.

Alternatively a hybrid scheme such as RSA-KEM combined with a block cipher could be used.

Deterministic encryption cannot be fully CPA or CCA secure; some kind of randomness or at least uniqueness is required to be CPA / CCA secure to not leak information for repeated messages.


How difficult is it to check if a group element is in a sub group? I am just curious. We have a group $G$ and its subgroup $H$ with a generator element $h \in H$. How difficult is it to check for $x \in G$ that $x \in \langle h \rangle$? Is there a better way than testing $x \equiv h^1,\ x \equiv h^2,\ x \equiv h^3,\ ...$?

If the group $G$ is finite and cyclic (and hence Abelian), it has exactly one subgroup of order $s$, for each $s$ which divides the order of $G$.

Since any subgroup of a cyclic group is also cyclic and hence Abelian, you might easily implement the operation in $H$ that is the equivalent of modular exponentiation in $Z_n^*$.

If you also already know the order $s$ of $h$, you know that, because of associativity and commutativity, that $(h^s)^t = (h^t)^s = 1$ for any $t$. Hence, checking that $x \in H$ is just a question of checking that $x^s = 1$.


Understanding SSL vulnerability within Apple's GOTOFAIL Currently learning and reading about the fascinating SSL Key Exchange and came upon the Apple GOTOFAIL incident back in 2014. I'm going through the code during that time and came across this section.

err = sslRawVerify(ctx,
                ctx->peerPubKey,
                dataToSign,                              /* plaintext */
                dataToSignLen,                   /* plaintext length */
                signature,
                signatureLen)

I am not quite sure which portion of the SSL Key Exchange protocol this belongs to. It seems like it is trying to verify the public key, date signed, and signature, however I don't think I can recall any portion of the SSL protocol with these three components in one transmission.

As this is known to deny the certificates, it would make sense that this portion came across before(or during) the time when server sends the certificate over to the client.

What exactly is 'sslRawVerify' doing?

here is a post with more detailed code.

Thanks!

I am not quite sure which portion of the SSL Key Exchange protocol this belongs to.

The webpage you link to shows this call in a function named SSLVerifySignedServerKeyExchange. Given that ServerKeyExchange is a message in the SSL/TLS handshake that is normally signed (except for "anonymous" suites that don't authenticate the server which are rare), I'll go out on limb and guess that function does the verify logic for a signed ServerKeyExchange in SSL (and TLS). Especially since the full code performs exactly the logic specified in the protocol standards through TLSv1.1 for verifying a ServerKeyExchange (except for the bug).

  It seems like it is trying to verify the public key, date signed, and signature, however I don't think I can recall any portion of the SSL protocol with these three components in one transmission.

It is using the public key to (try to) verify the signature on the data signed, which has nothing to do with any date. If you look at the preceding code, dataToSign and dataToSignLen are the address and length of space that at this point contains (or would without the bug) for RSA concatenated MD5 and SHA1 hashes of (apparently) clientRandom serverRandom and signedParams, or for DSA or ECDSA the SHA1 hash. This is exactly the computation specified by TLSv1.1 et pred modified by TLS-ECC. The clientRandom serverRandom and signedParams come from outside this function so we'd have to look elsewhere to be 100% certain they are correct, but it seems very unlikely the programmer(s) would have used exactly the names in the protocol standards for something different.

The server public key is part of its certificate, which was received in the prior server Certificate message. The signature is part of the current ServerKeyExchange message. The actual data to sign is the hash(es), which are computed from the signed params which are in the ServerKeyExchange message and the client random and server random where were in the prior ClientHello and ServerHello messages respectively.

  As this is known to deny the certificates, it would make sense that this portion came across before(or during) the time when server sends the certificate over to the client

That's backwards. This bug causes the client to accept the server signature as valid, and thus the server as authentic, even if the signature is forged by an imposter that does not have (and use) the correct private key. Since it uses the public key from the server cert, it must come after the server cert is received (and usually validated) and ServerKeyExchange does come after server Certificate in the handshake sequence.


How can I break REDSHIRT / REDSHIRT2 encryption? Recently, a user on Gaming.SE asked a question about whether the user password in the video game Uplink could be modified after being initially set.  The game does not contain an option to change the password, and the password is repeatedly displayed in plain text throughout in the game.  Obviously, this is a problem if a user accidentally uses a valuable password.

The game stores the password in the save file, which could be edited, except that the save file is encrypted using Introversion's REDSHIRT encryption scheme.  How do the REDSHIRT and REDSHIRT2 encryption schemes work, and what is the decryption algorithm?

Be Aware: Details of REDSHIRT encryption have already been discovered and published:

http://www.mario-konrad.ch/index.php?page=14002
http://uplinkfan.blogspot.com/2011/10/getting-book-2-of-uplink-game-bible.html

I'm asking this question only to benefit future users.  I do plan to post my own answer, but I'll be happy to upvote and accept anyone who explains it better than I can.

I'm not going to explain this but after looking at redshirt.c; the core part of the program is that after skipping the header (which is "REDSHIRT" (9 bytes includes an ending null byte)), it has a loop which does:

int j;
j = (j & 0x7F) + (~j & 0x80);

Which, if you don't recognize it, maps 128-255 to 0-127 and 0-127 to 128-255. (I think this might be the same as swapping the nibbles of a byte.) and is the same as j = (j + 128) % 256.


Why FHE takes modulo space $\Bbb Z_p$ as $[−p/2,p/2)$ rather than $[0,p)$? Why doesn't FHE scheme see a modulus space $\Bbb Z_p$ as $[0,p)$ ?
Instead, it consider $\Bbb Z_p$ as $\left[-\frac{p}{2},\frac{p}{2}\right)$.

What's the concrete reason?
What happens if I use $[0,p)$?

The notation

Many works on FHE use a function of $a$ and $p$ giving how far above or below the nearest multiple of $p$ the quantity $a$ is. Craig Gentry and Shai Halevi note that quantity as $[a]_p$ in Implementing Gentry's Fully-Homomorphic Encryption Scheme (extended abstract in proceedings of Eurocrypt 2011). It replaces $((a+\lfloor p/2\rfloor)\bmod p)-\lfloor p/2\rfloor$. This $[a]_p$ belongs to $[−p/2,p/2)$.

Nathanael Black in Homomorphic Encryption and the Approximate GCD Problem (page vii) go as far as using $a\bmod p$ rather than $[a]_p$:

  $a\bmod p\;\;$ Denotes reducing $a$ modulo $p$ into the interval $(-p/2, p/2]$

which is equivalent to
$$(a\bmod p)=r\;\iff\;p\text{ divides }a-r\;\text{ and }\;r\in(-p/2, p/2]$$
(the difference in interval boundaries is immaterial for odd $p$).

Alternatively, that variant $[a]_p$ of $a\bmod p$ could be defined as $a-p\cdot\lceil a/p\rfloor$, where $\lceil x\rfloor$ denotes rational $x$ rounded to the nearest integer (rounding up for Gentry et al.). This is similar to the standard $a\bmod p\;=\;a-p\cdot\lfloor a/p\rfloor$.

For both the standard and alternate definitions of operator $\bmod$, it holds that:
$$\begin{align}
((a+b)\bmod p)&=(((a\bmod p)+b)\bmod p)\\
&=(((a\bmod p)+(b\bmod p))\bmod p)\\
\end{align}$$
$$\begin{align}
((a\cdot b)\bmod p)&=(((a\bmod p)\cdot b)\bmod p)\\
 &=(((a\bmod p)\cdot(b\bmod p))\bmod p)\\
\end{align}$$
$$\begin{align}
(a\bmod p)&\equiv a&\pmod p\\
((a+b)\bmod p)&\equiv a+b&\pmod p\\
((a\cdot b)\bmod p)&\equiv a\cdot b&\pmod p\\
\end{align}$$
Note: In the above the notation $r\equiv a\pmod p$ means that $p$ divides $a-r$, and needs no adaptation. It is recognizable from operator $\bmod$ by the use of an opening parenthesis immediately on the left of $\bmod$, and (sometime: or) the use of an $\equiv$ sign somewhere on the left of and paired with $\bmod$.

Why it is useful

With the alternate definition $[a]_p$ of $a\bmod p$ comes an additional useful property, that does not hold for the standard $\bmod$: when $p$ is odd, for all $a$, it holds that $[-a]_p=-[a]_p$. That also holds for large even $p$ and most $a$.

The concept allows an easy extension to signed numbers and subtraction of one of the simplest (partially) homomorphic encryption system: Paillier's encryption. All it takes is defining a modified decryption as $D'(c)=[D(c)]_n$ and restriction of plaintext range; see this.

In some FHE systems, $[a]_p$ matches a signed noise term algebraically added to a signal aligned to multiples of $p$, and $a-[a]_p$ is the pristine signal recovered from the noisy $a$, minimizing the absolute value of noise $[a]_p$.


Byzantine agreement and PBFT I have just gone through Feldman-Micali, Dolev-Strong, KatzKoo (basically, most of the literature behind Byzantine agreement), however all of their protocols take a really incredible amount of rounds.

Just now, I read about PBFT from CastroLiskov and I realize that they are making a byzantine consensus that just happens in three phases.

Can someone explain why these two line of work diverge so much?
Are they tackling the same problem of agreement?
Could we not use the construction from CastroLiskov to make byzantine agreement?

I guess you have read the wikipedia page completely, and seen that all of those works mentioned are referenced. And then you have to consider two things from today's point of view:

The sequence of those publications.
The assumpions made. e.g. Practical Byzantine Fault Tolerance (PBFT) by Castro and Liskov assume $n>3t$. But I don't know which other protocols you mean, or what kind of assumpions they are based on. I would speculate they try to get high confidentiality (but no certainty) but allow a higher number of corrupted machines.

So while adressing the same problem, using different assumptions can lead to different solutions. And of course, later works should be aware of the prior ones - which is impossible the other way around.

I don't understand your last question. Yes, that's exactly what it does - under certain conditions. But what are you getting at? A general solution for any number of faulty machines? That's impossible - because what would be the correct result if all are faulty? If all but one are faulty how do we know what is faulty and actually correct? In that case we are wandering into the area of the halting problm as well.


RSA prove $a^{\varphi(n)/g} \equiv 1 \pmod{n}$ I should prove that $a^{\varphi(n)/g} \equiv 1 \pmod{n}$, so I thought I would prove it with primitive roots but I got stuck. Here is the assignment:

  Let $p, q$ be primes such that $p \ne q$. Denote $n = pq$, $\varphi(n) = (p − 1)(q − 1)$, and $g = gcd(p − 1, q − 1)$. Prove that

  $$a^{\varphi(n)/g} \equiv 1 \pmod{n} ~ ~ \text{for all} ~ a ~ \text{satisfying} ~ \gcd(a, n) = 1$$

Any help/hint would be great. Thanks.

Hint: try to prove that $a^{phi(n)/g} \equiv 1 \pmod p$ for all $a$ satisfying $gcd(a, n) = 1$.

Metahint: $phi(n)/g = (p-1) \times (q-1)/g$; is $(q-1)/g$ an integer?


Share secret non-interactively in a verifiable way In an application, I need to share a secret (random number) with a Group of known receivers over a public channel (a Blockchain) but each receiver needs to be able to check that the others received the same secret and if not will ignore the message. The problem is that the other receivers may not be online right now and thus an interactive protocol is not an option. The end goal is that all recipients get the same secret or all recipients ignore the message.

One solution I came up with is that after a recipient decrypted its part and received the secret he encrypts it with the public keys of the other recipients and checks that the cyphertext is the same, but this requires that the encryption scheme is deterministic but I only found probabilistic schemes and explanations why deterministic schemes are bad (but the concerns seem not to be a problem in my case as the plaintext is always a random number).

Is there a ready available deterministic asymmetric encryption scheme?
In other parts of the system, I use ECDSA so if I could reuse these keys it would be optimal but adding another scheme would be possible as well.
I'm not a cryptography expert and unless there is no other way I would like to avoid changing an existing scheme to make it deterministic.

Another option I found was using zero-knowledge proofs like SNARK, STARK or Bulletproofs but this seems like overkill and extremely complicated to pull off.

Are their other options I missed?

After looking a bit more into it I found a solution which I think should work.
I combined ECDH with AES todo the following:
Message Generation

I generate a new Elliptic Curve key pair (sesPk, sesSk)
I generate a key for each receiver: key_i = ECDH(sesSk, receiverPk_i)
I generate a message for each receiver: msg_i = AesEnc(key_i, sesSk||secret)
I combine the messages: msg =  sesPk||msg_0||...||msg_n

Secret Extraction

I generate my key: key_i = ECDH(mySk, sesPk)
I decrypt my message: sesSk||secret = AesDec(key_i, msg_i)

Secret Verification

I generate all keys: key_i = ECDH(sesSk, receiverPk_i)
I decrypt all messages: sesSk_i||secret_i = AesDec(key_i, msg_i)
I verify that all received the same secret: secret == secret_0 == ... == secret_n
I verify that all used the same session key: sesSk == sesSk_0 == ... == sesSk_n

Reminder

msg is shared over a blockchain so all receiver see the message or none does
receiverPks are known beforehand and thus are not included in msg but they could if necessary

If someone sees a weakness in this approach please share in the comments.


Does AES-CTR require an IV for any purpose other than distinguishing identical inputs? I'd like to encrypt files deterministically, such that any users encrypting the same plaintext will use the same key and end up with the same ciphertext. The ciphertext should be private as long as the plaintext is.

I plan to use AES-128-CTR with an IV of 0 and the SHA-256 of the plaintext as the key.

IV values are required to produce different output with the same key, but I am explicitly avoiding that behaviour here. I have heard that some ciphers/modes of operation also require the IV to provide randomness for the algorithm and that using an unrandom value (like zero) can be dangerous.

Aside from the repeatable output, is there any danger in using AES-128-CTR with an IV of zero?

Having done a bit more reading, here's my current understanding; verification or corrections appreciated:

NIST SP800-38A §6.5 describes CTR mode as just XORing each plaintext block with the result of ciphering the counter value with the key (where the initial counter value is called the IV).

If the a key is reused with the same IV (or a numerically-close one), this will will produce duplicate values in the stream with which your plaintext is hashed. This presents a large weakness to any attacker who can obtain multiple ciphertexts.

In my specific case, because I'm using a key that's unique to the plaintext it will have a unique stream of data to be XORed with the plaintext, making it secure.

The choice of zero for the IV is as theoretically dangerous as any other constant.

Well, no, in your case, a constant IV is not a problem.  With counter mode, the rule is that you cannot reuse the same IV with the same key.  However, it is perfectly fine to use the same IV with different keys, and that's what you're doing.

One minor correction to what you have (that doesn't directly relate to your question): you state that there are problems if "a key is used with the same (or a numerically-close one).  Actually, as long as the IVs are different, "numerically-close" IVs are not an issue.  In fact, it is actually pretty common to select counter mode IVs using a message counter (e.g. the first message gets IV 0, and second one gets IV 1, etc.)

However, I do have one question: how do you expect someone to decrypt the ciphertext?  If what you're doing is generating a hash of the plaintext, why don't you just go with the SHA-256 hash of the plaintext?


What are the implications of the new alleged key recovery attack preprint on SIMON? Just recently, a new attack was published against SIMON-32/64 which claims to also be applicable to other versions of the cipher. The paper is titled A Note on SIMON-32/64 Security (archived 2019-05-11) and describes a new practical, low-cost key recovery attack which is significantly faster than exhaustive search. Unfortunately, the authors spend more time describing a zero-knowledge proof that allows them to refuse to publish their analysis methods than in actually describing their analysis.

Abstract: This paper presents the results of a new approach to the cryptanalysis of SIMON-32/64, a cipher published by NSA in 2013. Our cryptanalysis essentially considers combinatorial properties. These properties allow us to recover a secret key from two plaintext/ciphertext pairs, in a time ranging from a few hours to a few days, with rather limited computing resources.
The efficiency of our cryptanalysis technique compared to all known cryptanalyses (including key exhaustive search) is a justification for not revealing the cryptanalysis techniques used. We have adopted a zero-knowledge-inspired method of proof which was initiated in [11].

Given only what is known so far, what are the implications of this attack? Does it apply to any SIMON-like block cipher, or is it a general technique that works on a large number of different ciphers?

TL;DR: this paper seems to be a joke, or delusional; the "zero-knowledge proof" proves nothing.

The report purports to have found an efficient cryptanalysis on SIMON-32/64, a small block cipher. The exact details are, on purpose, not disclosed. However, to convince the reader that the method actually exists, a so-called "zero-knowledge proof" (not really what is usually called zero-knowledge, by the way) is presented in section 4. What I will show here is that this proof shows nothing, and the same kind of feat could be relatively achieved with any block cipher with the same block size.

SIMON is a family of block cipher. Here, we talk about the "smallest" of these, SIMON-32/64, which has blocks of 32 bits and keys of 64 bits. The block size is important here: it means that when the article shows 64-bit plaintexts and ciphertexts, these really are pairs of plaintext blocks and pairs of ciphertext blocks, encrypted in ECB mode.

Let's see the first kind of "proof": the paper shows a few keys that encrypt the plaintext "YHWHYHWH" into the ciphertext "YHWHYHWH" (using ASCII encoding for both). As explained above, these really are keys that encrypt "YHWH" (32-bit plaintext block) into "YHWH" (32-bit ciphertext block); the repetition is a mere distraction. If you find a key that encrypts a given 32-bit block $P$ into a given 32-bit ciphertext block $C$, then of course the same key will encrypt $P\mathbin\|P$ into $C\mathbin\|C$, and $P\mathbin\|P\mathbin\|P$ into $C\mathbin\|C\mathbin\|C$, and so on. This is what ECB mode means.

Now, take a given plaintext block $P$, and a given ciphertext block $C$. How hard is it to find a matching key? If you take a random key $K$, the encryption of $P$ with key $K$ yields a ciphertext block $C'$, which has size 32 bits. Thus, the probability of having $C' = C$ is about $2^{-32}$. Which means that if you try random keys, you'll need on average to try about $2^{32}$ keys to find a match. Any decent-sized laptop should be able to try about $2^{25}$ keys per second (I am assuming here that encrypting a block takes 400 clock cycles, the CPU runs at 3.2 GHz, and there are four cores; we can probably do a lot better than that with AVX2 capers, but let's focus on stupid, basic software). Thus, $2^{32}$ keys will be tried in about two minutes. In other words, if you ask me to find keys that encrypt "YHWHYHWH" into "YHWHYHWH", then I should find one every two minutes. The six keys presented in the article represent less than 15 minutes of work of a single laptop! And all of that is using SIMON-32/64 as a black box, i.e. assuming that it is a perfect, ideal block cipher.

Now, let's investigate the second "proof": the authors take a large corpus of 64-bit messages (pairs of blocks), extracted from the King James Bible. In raw UTF-8 text (really, ASCII, it's all in English and does not contain the word café), this is a 4452069 bytes file. This means that there are 4452062 sequences of 8 bytes in there. Let's round that low to $2^{22}$ to make computations easier. The "proof" is that they show keys that map one of these blocks to another of these blocks; the table 6 shows 18 such plaintext/ciphertext/key triplets (the text of the article says "19" but there are only 18 in the table).

Take a perfect ideal cipher with 64-bit blocks (here we are not even going to use the fact that SIMON-32/64 uses 32-bit blocks and that 64-bit messages are really pairs of 32-bit blocks). Take a random key. Encrypt one of the $2^{22}$ plaintext blocks into a 64-bit block. What is the probability that the output 64-bit block is one of the $2^{22}$ in the list? It's $2^{-42}$ (because there are $2^{64}$ possible 64-bit blocks and $2^{22}$ targets). This means that if you try random keys, you'll get a match every $2^{42}$ random keys on average. At $2^{25}$ per second, we're talking about one key every two days; the 18 keys will then take a bit more than a month. The authors claim to have required 120 days, so they're a bit lagging here. Again, taking the block cipher as an ideal black box, a basic brutal attack does better than the cryptanalysis claims.

(With some details: some basic optimization here is that the "attack" will only encrypt one 32-bit block to start with, and encrypt the second one only if there was a match with the first one; moreover, the lookup in RAM for a match can be optimized by doing it only if the output block is ASCII, i.e. if the top bits of each byte are zero, so we end up with, for each key: one SIMON-32/64 encryption, a test on the top bits of the output bytes, a lookup into RAM only in 1/16th of cases, and a second block encryption only in 1/64th of the cases were a lookup in RAM is done; thus, we can easily approximate the cost as "1 SIMON-32/64 encryption per try".)

So whatever they are doing, it does not seem to be any better than brute force that has nothing to do with the internal structure of the block cipher.

An open question is whether this is a deliberate prank, a skewed attempt at damaging the reputation of the eprint maintainers, or a case of self-delusion. I don't attempt to answer that question.


Do all forms of symmetric encryption require multiple pieces of information? (nonce, iv, etc) I'm attempting to learn encryption and have a very basic grasp of it, but I have questions.

First, I'm looking to use AES.

I want to take text, encrypt it with AES using a variable-length key, and return encrypted text.  Then I'd like to pass in the encrypted text, the key, and get the original text back.  In other words: a Symmetric cipher.

It seems every AES mode that I can see requires a piece of data for decryption that seems problematic to store.  For instance, EAX has a nonce that needs stored.  CFB has an Initialization Vector (iv) that needs stored.

The way I see it is that I can store the iv in a second location from the encrypted text or I can generate the iv predictably every single time.

Is it considered secure to store the iv or nonce?

The way I see it is that I can store the iv in a second location from the encrypted text or I can generate the iv predictably every single time.

Actually, if you don't mind the ciphertext being longer than the plaintext, we can just include the IV/nonce in with the ciphertext.  What we typically do is place the IV/nonce at the front of the ciphertext, and place the output of the block mode right behind it.  This means that the ciphertext is 8 to 16 bytes longer; for most use cases, we can live with that.  We generally also want to store some sort of integrity tag as well (so that if someone modifies the data, we can detect it); that extends the ciphertext a bit more.

Of course, there are some use cases where the ciphertext must be exactly as long as the original plaintext (for example, if we're storing the encrypted data somewhere that was originally intended to store the plaintext, and so the space available to store data is limited to the expected size of the plaintext; this comes up both with encrypted databases and encrypted disk drives).  We could, in this case, store the IV/nonce (and the integrity tag) elsewhere, however (in my experience) that's rather rare.

There are specialized modes that are designed to work with the constraint that the ciphertext is exactly the same length as the plaintext, such as XTS (generally used for disk sector encryption) and Format Preserving Encryption modes (designed for encoding small pieces of data, such as a credit card number); unless you require something that needs to live with this constraint, this is typically not the correct solution.

  I can generate the iv predictably every single time.

Modes that use IV/nonce are typically badly behaved if you encrypt two plaintexts with the same IV/nonce; with EAX mode, you allow the adversary to deduce the XOR of the two plaintexts; with CFB mode, you allow the adversary to deduce how many blocks the plaintexts agree and on the block they first disagree, the XOR of those two blocks.  Hence, generating the IV predictably every single time is generally not the correct solution.