Is there a way to verify an original author using encryption? I feel like the title explains the problem fairly well. Is is possible to use encryption to verify a document's original author? In my case, I have a doc that I want to release online. Is there a way I can make sure that anyone who finds the doc can verify that I was the original author who created it and not someone who just copied it?

Yesish, but only for cryptographic purposes within the scope of this forum.  My last bit will show that this isn't worth hill of beans legally, which also makes this question entirely off topic for practical purposes.

You could do this with a time stamping authority:-

All good fun for amateur cryptographers, but the problems start at step 1. A hash is performed of your original document.  Any good cryptographic hash (such as SHA-256) produces effectively unique outputs for any given input.  Even if the inputs only vary by one bit. So

H("Tankobot") ≠ H("Tankobot ")

There's an extra space at the end of the second hash.  The little bits of the two hash outputs will be approximately 50% different. This is due to the avalanche effect inherent in all respectable hashes.

The negative consequence of this is that your plagiarised work will have to be word for word, character for character and bit for bit the same as your original.  It will have to be in the same human language and the same computer character set.  You'll have to retype and re format the suspect work to then perform the validity check to prove ownership. The slightest variation will result in different signed hashes.

That's great for ASCII type text. If your document is graphical, there are sophisticated water marking techniques which are allegedly robust but have not really be field tested. Results for this are below, but I'm not sure how well noise robustness helps if the student redraws your document images:-

That's all wonderful and this answer stops here wrt cryptography.  In the real world, you're wasting your time.  You might as well post the document to yourself and pray. It might work if you catch a student cheating with homework and spank them.

In court, it's worthless.  This type of effort is termed Poor Man's Copyright.  Neither the courts or copyright offices of the UK nor US recognise these clever techniques.  The time stamp has zero evidentiary value in copyright terms.  Independent creation, derivative works and eye witness testimony of copying are some of the easy spanners that smash your system. This is an immense sector of law and I'm not qualified to provide advice. You'd better not be spanking any students as they can sue you if you can't prove they cheated in court.


Can a ciphertext be decrypted to 2 meaningful messages? Suppose I have two messages $M_1$ and $M_2$ and I have two different symmetric keys $k_1,k_2$.

Is it possible to achieve this?

$CipherText(M_1)_{k_1}$ = $CipherText(M_2)_{k_2}$

Edit: Im asking for standard ciphers used in practice, not for theorical ones.

This is actually possible in practice because to us, human beings, a "meaningful message" can be a file.

Now, depending how we encrypt our files, we have more or less slack variables at hand to play around with the resulting ciphertexts.

Ange Albertini played a lot with file formats and he actually has a PoC where he encrypts given images into other files, even valid images... Or where he encrypts a JPG into a PNG if using AES and into a PDF if using 3DES... Or even worse!

(image by Ange Albertini, CC3.0BY)

How comes? Well, this is mostly done by abusing the way the modes of operation work, as well as the way the file formats work.

When you encrypt a file using AES CBC, for instance, you can choose your IV, which means that you can control the first 128 bits of your ciphertext. Furthermore you can also append any plaintext data at the end of your ciphertext, and it will get encrypted when you decrypt your ciphertext, but it also means that you can obtain its corresponding ciphertext so that it gets decrypted when you encrypt your plaintext appended with that ciphertext...

With this two details you already have plenty of room to play around with the file formats in a way that would produce valid files when encrypted/decrypted!

Now, a question that was not addressed by Ange is whether this is secure...
Well, as long as you are appending encrypted data or that you are not reusing your IVs, this does actually protects the content of your files (especially Ange's limited deniability example), as long as your secret key remain secret... (But it might be a problem in the case of CBC, depending on your use of the cipher, as it mandates most of the time the IVs to be unpredictable, unlike CTR where it suffices to have unique nonces.)

So, is it possible to do the same in the other direction, decrypting into two different files given different keys? Well, if you can have different IVs, then yes, it is possible using the same kind of tricks that Ange used.

In the end, is this related to the way the actual ciphers work? No, not at all. This is not a cryptographic property, but a consequence of the file formats' malleability.


Public-private algorithm where it is not possible to recover public key from private key? Is there an asymmetric algorithm where it is not possible to extract a public key from private key? So far any algorithms I tried (dsa, rsa, ecdsa, ed25519) successfully recover their public keys from private ones with 'ssh-keygen -y -f private.key'.

RSA as initialy described (R.L. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in CACM, 1978) has this property that it is impossible to find the public key $(N,e)$ from the private key expressed as $(N,d)$. For modern parameters, pick random primes $p$ and $q$ in range $[2^{2047.5},2^{2048}]$, pick random $4095$-bit $d$ with $\gcd(p-1,d)=1=\gcd(q-1,d)$, compute $N=p\,q$ and $e=d^{-1}\bmod((p-1)(q-1))$, keep the private key $(N,d)$ and separately the public key $(N,e)$, but destroy $p$, $q$, and $(p-1)(q-1)$.

Note: While that original RSA system does not allow "to extract a public key from private key", it is still possible to test if public and private key match; that seems unavoidable for any public-key cryptosystem, be it for encryption or signature.

Modern RSA has $e$ (and often $p$ and $q$) in the private key, because

it is generally a feature that the public key can be extracted from the private key
having $p$ and $q$ allows to speed up private-key operation considerably
having $e$ allows to verify computations made with the private key, which is useful to guard against some attacks.

Also, modern RSA typically uses small $e$ (often $2^{(2^k)}+1$ for $0\le k\le4$) and that makes guessing $e$ and verifying the guess trivial.


What does DH(IPKa, IPKb) notation mean? Diffie-Hellman confusion I'm trying to implement X3DH (extended triple Diffie-Hellman) in a network of mine.
The way I understand it, a bundle (IPKb,SPKb,OTKb) is retrieved by Alice from Bob, through the server, and
using her own public keys IPKa and EPKa she calculates:
DH(IPKa,SPKb)
and some others.
What I do not understand is: what are these public parameters used for in DH? Isn't Diffie-Hellman constructed with private keys, and 2 pre-determined public numbers? Should I treat these 2 keys as those pre-determined numbers?
Also, Diffie-Hellman requires key exchanges and communications between Alice and Bob; why can't Bob compute the key at the same time as Alice? Why does Alice need to return a bundle of her own IPK and EPK for Bob to do the calculations from scratch? I'm confused.
Sorry for the naive question but I can't seem to find an explanation on what these passed keys are supposed to be doing anywhere.

As X3DH uses elliptic curve Diffie-Hellman, I'll write things in elliptic curve notation thus if we have a curve $E$ with $q$ points and a base point $G$ we might see Alice choose a private key $a\pmod q$ and create a public key $A=aG$. It should be easy to convert to multiplicative notation if you need to.
Regular Diffie-Hellman
In the regular form of the Diffie-Hellman, Alice and Bob each choose a single private value $a$ and $b$ respectively, and generate public keys $A=aG$ and $B=bG$ which they then exchange. In the notation of the question
$$\mathrm{DH}(A,B)=aB=bA=abG$$
is the shared secret value. Although it is written as a function of $A$ and $B$ this is in a mathematical rather than a computational sense. It should be infeasible to compute $\mathrm{DH}(A,B)$ without knowledge of one of the private values. This notation can be frustrating.
People talk about static Diffie-Hellman and ephemeral Diffie-Hellman depending on whether the same values are used over multiple exchanges or whether new values are generated for each exchange. Static Diffie-Hellman gives some assurance that you are communicating with the same person in both exchanges. Ephemeral Diffie-Hellman prevents the same key being generated and provides forward security which is the assurance that if a private key becomes known, it only jeopardises a single message rather than any previous ones.
X3DH
X3DH tries to create keys with the benefit of both the static and ephemeral versions. It has Alice and Bob choose multiple secret values and public values, say $a_0$, $a_1$ etc. and perform multiple DH computations to combine the results. In particular, they both create long term identity keys $IK_A=ik_AG$, $IK_B=ik_bG$; they create medium term signed keys $SPK_A=spk_AG$ and $SPK_B=spk_bG$ which change from time-to-time but are digitally signed so that users can be assured that they are only used by the claimed user; they create several one-time-keys. In particular then
$$\mathrm{DH}(IK_A,SPK_B)=ik_ASPK_B=spk_BIK_A=ik_Aspk_BG$$
and
$$\mathrm{DH}(EK_A,IK_B)=ek_AIK_B=ik_BEK_A=ek_Aik_BG$$
Thus there is a measure of both identity assurance and separation of key values.
The X3DH protocol is designed so that Alice can initiate communications even when Bob is offline and so it makes sense for Alice to perform her half of the computation and send it even if Bob is not present. Bob can then complete his half of the transaction when he comes online and deals with Alice's message.


Understanding Quantum Key Distribution I have watched dozens of videos on YouTube talking about quantum cryptography and how the BB84 algorithm works. However, none of them bothered to explain how the quantum key exchange process works in detail; that is, for newbies like me. Thus I still have many unanswered questions.
Given the following scenario where Alice is the sender and Bob is the receiver:
1- How Alice and Bob agree on which of the two beam-splitter bases (Horizontal-Vertical and Right-Left) correspond to which classical bits (1 and 0)? How do Alice and Bob agree on when actual transmission starts, when it is time to send/receive a photon taking note of an event?
2- I understood that once Bob has measured all of the photons sent by Alice, he would record the list of the beam-splitter bases he used to measure those photons and send this list to Alice to check his bases against hers. If Alice finds a match, she would tell Bob to use the received qubit state as part of the key. Otherwise, she will tell him to discard it. Right?
3- If point two holds correct, I would like to know how Alice could detect an eavesdropper, Eve, and warn Bob about that based on Bob's beam-splitter bases list?
4- Where does Heisenberg's Uncertainty Principle come into action in QKD?
I hope to get some detailed answers.

How Alice and Bob agree on which of the two beam splitters bases (Horizontal-Vertical and Right-Left) correspond to which of the classical bits (1 and 0) ? How do Alice and Bob agree on when actual transmission starts, when it is time to send/receive a photon taking note of event ?

Alice and Bob operate according to an agreed-upon protocol, which can define what binary value is assigned to what is physically made or observed, perhaps as follows:

Image source: UNS Nice (France), Department of Physics
There remains to agree on conventions in physical orientation, in particular what's rectilinear and what's diagonal (the optical link can rotate things); and the sequencing of sending photons and moving polarizer in-between.
Sequencing can be using an agreed-upon amount of time between photon emission, with the move of polarizer occurring in-between. Both that sequencing and the orientation can be determined by having Alice conventionally sending a repeating pattern before start of transmission, which allows Bob to calibrate it's receiving gear and reach synchronization (in particular rotate polarizer at a moment when that won't prevent detection of photons). The start of actual transmission can be determined by an agreed-upon and detectable change in the sequence, e.g. start right after
|/−\||/−\||/−\||/−\||/−\||/−\||/−\||/−\||/−\||/−\||/−\||/−\||/−\|−\|/−
The beginning has period 5 and allows to find what's what. The last 5 photons are rotated compared to the continuation of the sequence, which provides a robust indication of start to Bob having reached synchronization.

Once Bob has measured all of the photons sent by Alice, he would record the list of the beam splitters bases he used to measure those photons and send this list to Alice to check Bob's bases against hers. If Alice finds a match she would tell Bob to use the received qubit state as part of the key. Otherwise she will tell him to discard it. Right?

Yes. Note that the transmission of binary information from Bob to Alice, and back, occurs over a classical (non-quantum) public channel which authenticity typically is insured by conventional information-theoretic cryptography using an agreed-upon one-time-use shared key (see section B.3 in that answer) That key can be renewed by sparing a fraction of what's established by a step of Quantum Key Distribution, in order to secure the next one.

How would Alice detect that there was an eavesdropper Eve and warn Bob ?

The determination that there was no foul play is made by some highly technical "secret-key reconciliation" and "privacy amplification" protocol (running over classical channels authenticated as in 2 and allowing Bob to positively confirm success to Alice, or/and vice versa). Complex but conventional error-detection and correction techniques are involved. Basically, if the error rate of the quantum channel is sufficiently low, Eve can't have learned enough of it to compromise the confidentiality of the key obtained thru this protocol. See sections B.1 and B.2 of said answer for more.

Where does Heisenberg's uncertainty principle comes into action in QKD?

This  principle asserts that a photon's polarizations according to diagonal and rectilinear directions can't be both determined by an observer. That prevents Eve from reliably determining the state of Alice's photon and sending an exact copy to Bob: in her attempt at that Eve is bound to make at least 50% error for the polarization she could not observe, that is 25% error overall at the bit level, and that's detectable per the protocol of 3).


Curve25519 key exchange in detail So I'm trying to understand how the key exchange with Curve25519 works. I read the original Paper from Bernstein "Curve25519: new Diffie-Hellman speed records", but I still got some questions. First of all, this is graphic, how the key exchange should work:

So Alice and Bob create their own secret key by randomly choosing a number $$n\in 2^{254} + 8 \cdot \{ 0, 1, \ldots , 2^{251} - 1\}.$$ In other ECC standards, this $n$ is multiplied with a Public Point $P$, but here I don't have a public Point $P$. So that's where I don't understand the concept.

The Public string is not a point, it is a number $q \in \{0,1,\ldots,255\}^{32}$ and i don't understand, why it is only a number and not a Point.

So in other Standards, the public key of Bob and Alice is produced by multiplying the secret key with the public Point. That produces new Points, which are the public keys.

Here there is a public function also included I have no idea, what it does. That means, I can't figure out, how the shared secret key is produced.

In addition, I would like to know what the functional call of $\operatorname{Curve25519}(a,9)$ means, so what do the parameters do with my curve?

Can someone explain this to me? Is it possible to give me a simple example of how it works?

TL;DR: The public key is not a point, it is the $x$-coordinate of the point.

The base point of the curve has been chosen to be the point $G = (9,y_0)$ with $y_0>0$, and the curve Curve25519 is used in its Montgomery form given by the equation
$$
y^2 = x^3 + 486662x^2 + x.
$$
The main operation on elliptic curves is the scalar multiplication, and in this case, it is computed with the Montgomery ladder algorithm with formulas that use only the $x$-coordinate of the input point, and output the $x$-coordinate.

For one valid $x$-coordinate of a point $P$, there are two possible points, $P$ or $-P$, so if Alice private key is $a$, then her public key is $x([a]G)$ (the $x$-coordinate of the point $[a]G = G + G + \cdots + G$, the output of $\operatorname{Curve25519}(a,9)$). Since the $y$-coordinate is not used, then it corresponds either to the point $[a]G$ or $-[a]G$, then Bob can compute easily $x([ba]G)$, which corresponds to either $[ab]G$ or $-[ab]G$.

Basically, the $y$-coordinate is not useful to get a shared secret, and not useful for the computation since the formulas that do not use it on Montgomery curves are pretty efficient.


Shamir Scheme: Whats the problem of not using random x-coordinates? i would like to know why there is a problem of not using random x-coordinates in shamir secret sharing schemes.

I consider that after evaluating the points in a polynomial $f(x)$, the share is composed by: $(x, f(x))$, where the $f(x)$ is secret and the $x$ could be public. So, why i always find in some literature that it is a problem using not random x coordinates? Could i have an example of why is it a problem?

Associating the shamir scheme with ortogonal arrays (respecting the strength and lambda properties), i know that fixing the x-coordinates i am restricting the matrix to only the known columns and, consequently, we have a smaller matrix. But we still have the perfect privacy properties, because even knowing the x-coordinates, each secret appears exactly the same quantity of times for each t-tuple, where $t$ is the threshold. Therefore, even knowing the x-coordinates, i can not know anything about the secret.

i would like to know why there is a problem of not using random x-coordinates in shamir secret sharing schemes.

There is no such problem.

The only requirements on the $x$-coordinates are:

They're all in the range $(1, p-1)$ (or $p^k - 1$ if you're using the extension field $GF(p^k)$; you can't use 0 as a coordinate (as $f(0)$ is the secret), and you can't you values outside the range.
They're distinct (if they're not, then the two shares with the same $x$ coordinate are the same share).

ANy arbitrary set of $x$-coordinates that meet these two requirements work just fine.

  So, why i always find in some literature that it is a problem using not random x coordinates?

I suspect that you are misinterpreting the literature.  For the coefficients of the secret polynomial $f(x)$, it is necessary that the non-constant terms be random; if they are not, then it is possible for a small group to recover the secret.

There is no corresponding requirement on the $x$; they can be any values you find convenient (as long as they meet the above two requirement)


AES-128: can any two keys generate the same ciphertext from the same plaintext? This is a purely theoretical question. I've found some similar questions, but they're not what I'm asking.

Most importantly, I'm not asking whether anyone can find the hypothetical duplicate. I'm not asking about the probability of encountering a collision, or how long it would take. In short, for my purposes, pretend you're coming to this from a non-crypto math background, and consider all finite numbers to be small, and imagine that you're allowed to do exhaustive searches of any finite space.

For any given key, there is obviously a 1:1 mapping from plaintext to ciphertext.

Now, consider a specific fixed plaintext. There are 1<<128 possible keys. There are 1<<128 possible ciphertexts.

Either there's exactly one key that produces each ciphertext, or at least one ciphertext results from at least two keys, and at least one ciphertext results from zero keys.

If you imagine AES as simply selecting random permutations, this is the birthday problem, and it's effectively certain that there are duplicates -- at least two keys will produce the same ciphertext from your given plaintext, and at least one ciphertext will never occur from that plaintext.

But AES doesn't select random permutations. It selects pseudo-random permutations. The selection process can't select every possible permutation; it can only select some of them. And it is conceivable that the set of permutations it can select has such a trait.

It is trivial to devise a scheme which produces non-overlapping permutations, as long as the number of keys doesn't exceed the number of possible plaintexts. For instance, "treat key and plaintext as unsigned 128-bit values, add them, that's your ciphertext" would have this property.

I have no practical applications for this, but if you want an impractical application: If AES did have this property, then you could interchange the roles of key and plaintext. You could send people blocks that were AES encryptions of a known plaintext, and they could simply look up the key in their table of "which key produces each ciphertext from that fixed plaintext". (Sadly, that table appears to require more storage space than our universe has atoms, but practicality is not my strong suit.)

EDIT: I did find AES-128. Do there exist two different keys for a pair (text, encrypted text)?, but I think that answer contains a flaw, which is that it assumes that the permutations are random, and that the way they are generated isn't influencing the selection of permutations, for instance, making them less likely (or more likely!) to overlap. I'm questioning that underlying assumption.

Specifically, it's this bit here:

  What if instead of uniform random πi we had πi=AESki for uniform random strings ki? If you could predict how that would affect the distribution nonnegligibly, you could distinguish AES from a uniform random permutation, violating the pseudorandom permutation family property that it is conjectured to exhibit, and there would be lots of cryptographers who would like to have a word with you.

(sorry for cut and paste formatting)

This isn't right, though. Think about block-cipher mode with a fixed key, and cycling through the (1<<128) possible plaintexts. You can't distinguish the output from a series of 128-bit random values in any way... But with an actual series of 128-bit random values, you'd virtually certainly get at least one duplicate by the time you did all the inputs, and with AES-128, you won't. But that's the only observable distinction, so far as I know. There's no ranges that are more or less likely, there's no connection from one to the next, and yet, you will somehow just magically never hit a duplicate value.

So we already know that AES-128 has, in one context, the weird property that a series of values it generates is indistinguishable from a random series of 128-bit values, with the sole exception of "but you never get a duplicate until you've hit everything". I'm wondering if it might have that property in a different direction also.

So we already know that AES-128 has, in one context, the weird property that a series of values it generates is indistinguishable from a random series of 128-bit values, with the sole exception of "but you never get a duplicate until you've hit everything". I'm wondering if it might have that property in a different direction also.

Highly unlikely.  The weird property you point out was actually a design goal of AES (actually, of any block cipher), and is fairly easily seen if you open up the hood of AES and look inside - it's the concatenation of a number of fairly trivial permutations, and concatenating permutations together always gives you a permutation.

In contrast, it was never a design goal that two different 128 bit AES keys never map the same plaintext block to the same ciphertext block; as you point out:

  But with an actual series of 128-bit random values, you'd virtually certainly get at least one duplicate by the time you did all the inputs

So, unless AES-128 has some special properties that no one (even the designers) expect, there is almost certainly two keys that map one particular plaintext block to the same ciphertext block.


weaknesses in ElGamal with public key of small order Suppose $p=29$, $\alpha = 2 \in F_p^*$ is a generator of $F_p^*$. Bob picks $d \in \{2,...,27\}$ such that $\beta = \alpha ^d=28 \pmod{29}$. He then sends his $(p,\alpha ,\beta)$ to Alice who herself picks one $i_j \in \{2,...,27\}$ for eleven different plaintext values $m_j$, $0\leq j\leq 10$ and encrypts these by $c_j=m_j*28^{i_j} \pmod{29}$.
Since $|28|=2$, the only possibilities for the masking key $k_M = 28^{i_j} \pmod{29}$ are $1$ and $28$.

Alice sends the following ciphertext-key pairs in the form $({k_E}_j, c_j)$:
$$(3,15),(19,14),(6,15),(1,24),(22,13),(4,7),(13,24),(3,21),(18,12),(26,5),(7,12)$$
where $a=0, ..., z=25, ä=26, ö=27, ü=28$. We thus have the ciphertext
$$p,o,p,y,n,r,y,v,m,f,m$$
The task is to decrypt the message without computing Bob's private key, by "looking at the ciphertext and using the fact that there are only very few masking keys and a bit of guesswork". Since the only possibilities for $k_M$ are $1$ and $28$, the plaintext corresponding to $c_j$ is either $c_j$ itself or $c_j*28^{-1} \pmod{29}$. This yields two possibilities per $c_j$:
$$p,o,p,y,n,r,y,v,m,f,m$$
$$o,p,o,f,q,m,f,i,r,y,r$$
I could not make sense out of the two, so I computed Bob's private key anyways to check the result. It turns out Bob's private key is $14$ ($2^{14}=28 \pmod{29}$). Computing ${k_M}_j = {k_E}_j^{14}$, the result turned out to be
$$o,p,p,y,n,r,y,i,r,y,m$$which still does not make any sense to me.

So my question is: did I mix something up along the way? If not, where is the "guessing" supposed to happen? Also I have not used the fact that $\alpha = 2$.

EDIT

I seem to have been unclear before. I am asking this because this belongs to an exercise (decrypting the given ciphertext without calculating Bob's private key), and I believe I missed something. The actual result, calculated by using that not allowed key, seems random. So I don't know how guessing should be of any use, or how to decide which is the correct sequence without using the private key.

EDIT2

As suggested in the comments I'll quote the complete exercise here:

We investigate the weaknesses that arise in Elgamal encryption if a public key of small order is used. We look at the following example. Assume Bob uses the group $\mathbb{Z}_{29}^*$ with the primitive element $\alpha = 2$. His public key is $\beta = 28$.

i) What is the order of the public key?

ii) Which masking keys $k_M$ are possible?

iii) Alice encrypts a text message. Every character is encoded according to the simple rule $a=0,...,z=25$. There are three additional ciphertext symbols: $ä=26, ö=27, ü=28$. She transmits the following 11 ciphertexts $(k_E,y):$
(see the 11 pairs above)

Decrypt the message without computing Bob's private key. Just look at the ciphertext and use the fact that there are only very few masking keys and a bit of guesswork.

Thank you

Well, your problem is that you choose a specific bad private key ("-1"), which only generates a group with two elements. However, this is a very specific weak case, and the chance to select the according private key is negligible.

But in general, there are a couple of problems with choosing a generator for the whole group $\mathbb{Z}_p^*$, because it is leaking some information. For example, if $\beta$ is a quadratic residue, but $c=m\cdot \beta^i$ is not a quadratic residue, then $m$ is a quadratic non-residue.

The general solution is to use Schnorr groups, where the generator only generates a part of the multiplicative group, but has a large prime order itself (which is also the order of all elements except the neutral element).


How does Fialka manage to have a letter encipher unto itself? http://www.cryptomuseum.com/crypto/fialka/index.htm

Fialka was an electromechanical rotor machine.

How does it manage to have a letter encipher unto itself. I realize it does something clever by using transistors, but it has a reflector. With direct current circuits, there has to be a negative and a positive connector. If one simply attached a positive current to itself, it wouldn't flow. So how does it work?

The reflector wheel on the Fialka incorporates a transistor switching circuit connecting pins 16, 18 and 24. In coding mode, a signal on pin 16 is connected via pin 18, a signal on pin 18 is connected to pin 24, and a signal on pin 24 is connected to pin 16.  In decoding mode, these paths are reversed.  This allows the Fialka to encode any letter as itself, overcoming one of the major weaknesses of the Enigma machine.


What is meaning of "Decipher the rest of the message by deducing additional words"? I have an assignment in cryptography. I am not asking here answer, but meaning of question.

This is a question :

  2.4 The following ciphertext was generated using a simple substitution algorithm. 53‡‡†305))6*;4826)4‡.)4‡);806*;48†8¶60))85;;]8*;:‡8†83 (88)5†;46(;88*96*?;8)‡(;485);5†2:*‡(;4956*2(5*—4)8¶8* ;4069285);)6†8)4‡‡;1(‡9;48081;8:8‡1;48†85;4)485†528806*81 (‡9;48;(88;4(‡?34;48)4‡;161;:188;‡?;

Decrypt this message.
Hints:
1. As you know, the most frequently occurring letter in English is e. Therefore, the first or second (or perhaps third?) most common character in the message is likely to stand for e. Also,e is often seen in pairs (e.g., meet, fleet, speed, seen, been, agree, etc.). Try to find a character in the ciphertext that decodes to e.

The most common word in English is “the.” Use this fact to guess the characters that stand for t and h.
Decipher the rest of the message by deducing additional words. Warning: The resulting message is in English but may not make much sense on a first reading.

Some how I did answer for 1 and 2, but not able to understand 3rd question.

Does this mean, I should replace t, h and e characters and deleting rest??

"Deduce" = "guess, and test your guess"

You know where the letters t,h, and e are, so you might find a sequence "the-e". You can guess this will be "there" in the message, and then you have the substitution for r which you can also try, filling in more gaps and giving you essential clues for other words. If anything starts to look wrong, backtrack and revise one of your earlier guesses.

This is a lot like attempting a crossword, but the clues are the context of the words in the message.


Elliptic Curves and Small Message Space Let $G$ be the generator of an elliptic curve $E$ of order $n$. Let $M$ denote a small (say, size $2^8$) message space. Elements of $M$ are mapped to points in $E$; the mapping is considered public. Let $s$ be a randomly choosen (secret) number from $[1,n-1]$. For some $m\in M$, is it computationally tractable to recover $m$ from an encoding of the form $sG+m$?

Define $\mathbb{G} = \langle G \rangle$ the cyclic group generated by $G$.  The order of $\mathbb{G}$ is $n$.

In your scheme, an 8-bit message is encoded as a point $m = kG$.  An attacker gets access to the value of $sG + m$ for a random $s \in [0,n-1]$.  The question is: can the attacker recover the value of $m$ (and then the value of the corresponding message)?

The answer is no.  To see it, observe that the point $S = sG$ is a uniformly random element in $\mathbb{G}$.  As a result, the point $S + m$ is in turn a uniformly random element in $\mathbb{G}$.


Recommended key lengths for BLAKE2b RFC 7693 provides the following table of standard parameter sets for BLAKE2b without a key (where nn is the hash size in bytes):

|             | Collision | Hash |
| Algorithm   |  Security |  nn  |
+-------------+-----------+------+
| BLAKE2b-160 |   2**80   |  20  |
| BLAKE2b-256 |   2**128  |  32  |
| BLAKE2b-384 |   2**192  |  48  |
| BLAKE2b-512 |   2**256  |  64  |

However, for BLAKE2b with a key it only notes that the key length kk must be in the range 0 <= kk <= 64 bytes. The BLAKE2 documentation  doesn't seem to provide any more detail.

In RFC 2104, the definition of HMAC includes specific recommendations for the key length (where B is the block length and L the length of hash outputs of the hash function H):

  The key for HMAC can be of any length (keys longer than B bytes are
  first hashed using H).  However, less than L bytes is strongly
  discouraged as it would decrease the security strength of the
  function.  Keys longer than L bytes are acceptable but the extra
  length would not significantly increase the function strength.

Questions:

What are the recommended combinations of key length and output length for BLAKE2b as a MAC to get the usual 128-/256-bits of security?
What is a good way to estimate the bits of security provided by other combinations?
What is some good reading material that covers questions like this, since the audience of the RFC is clearly assumed to know such things?

The Analysis of BLAKE2's Modes of Operation paper gives a PRF bound for keyed BLAKE2b with a key of size $k$, under the assumption that the underlying block cipher is ideal (Corollary 3):
$$
\text{Adv}^{\mathrm{PRF}}_{\text{BLAKE2b}}(\mathcal{D}) \le \frac{q^2}{2^{1024}} + \frac{2q^2}{2^{512}} + \frac{q}{2^{256}} + \frac{q}{2^k}\,.
$$
Here, $q$ is the complexity of the distinguisher, i.e., calls to the hash function.

Given this PRF bound, the MAC security of BLAKE2b with output size $t$ can be derived as
$$
\text{Adv}^{\mathrm{MAC}}_{\text{BLAKE2b}}(\mathcal{D}) \le \frac{q^2}{2^{1024}} + \frac{2q^2}{2^{512}} + \frac{q}{2^{256}} + \frac{q}{2^k} + \frac{q_v}{2^t}\,,
$$
where $q_v$ represents the number of forgery attempts.

Seeing this, two things look clear:

It is pointless to have a key over $256$ bits, since security begins degrading by other means by that point.
The tag size influences the probability that a forgery succeeds; thus, it cannot be small enough that an attacker can succeed 'by chance'.

All in all, the same recommendations for HMAC also apply to keyed BLAKE2. A 256-bit key with a 128-bit tag seems like a reasonable choice for most purposes.


Needham–Schroeder fix by adding opponent's identity to the first message Recap: Needham–Schroeder is as follows:

$A \rightarrow B :   \{A, N_a\}_{pk_B}$
$B \rightarrow A :   \{N_a, N_b\}_{pk_A}$
$A \rightarrow B :   \{N_b\}_{pk_B}$

Then, there is a MITM attack by Lowe as follows:

$A \rightarrow C(A) :   \{A, N_a\}_{pk_C}$
$C(A)\rightarrow B     :   \{A, N_a\}_{pk_B}$
$B \rightarrow C(A) :   \{N_a,N_b\}_{pk_A}$
$C(A)\rightarrow  A       :   \{N_a,N_b\}_{pk_A}$
$A   \rightarrow  C(A)    :   \{N_b\}_{pk_C}$
$C(A)\rightarrow  B       :   \{N_b\}_{pk_B}$

Now $C(A)$ knows both $N_a$ and $N_b$, and he can compute the session key.
The solution that Lowe suggests is to put $B$'s identity to the second message:

$A \rightarrow B :   \{A, N_a\}_{pk_B}$
$B \rightarrow A :   \{N_a, N_b, B\}_{pk_A}$
$A \rightarrow B :   \{N_b\}_{pk_B}$

But what happens if we put B's identity into the first message?

$A \rightarrow B :   \{A, B, N_a\}_{pk_B}$
$B \rightarrow A :   \{N_a, N_b\}_{pk_A}$
$A \rightarrow B :   \{N_b\}_{pk_B}$

Is it still vulnerable to MITM attack or is it secure too?

It's easy to see that the man-in-the-middle attack you describe still applies to the modified protocol.

$A \rightarrow C(A) :   \{A, C, N_a\}_{pk_C}$
$C(A)\rightarrow B     :   \{A, B, N_a\}_{pk_B}$
$B \rightarrow C(A) :   \{N_a,N_b\}_{pk_A}$
$C(A)\rightarrow  A       :   \{N_a,N_b\}_{pk_A}$
$A   \rightarrow  C(A)    :   \{N_b\}_{pk_C}$
$C(A)\rightarrow  B       :   \{N_b\}_{pk_B}$

The idea why adding $B$'s identity to the second message might be helpful is that $B$ is telling the receiver who they are. So if $A$ sees that message they will realize that something is afoot, since they wanted to talk to $C$ but received a reply from $B$.¹

Whereas in your solution Alice tells the receiver who $A$ thinks they are. But since the man in the middle does not forward this message blindly, but in fact decrypts it and uses it to construct an entirely new message, this doesn't help in any way.

¹This only really helps if the public key encryption scheme used does not have malleable ciphertexts. Using encryption for authentication is just not a good idea and does not lead to robust solutions.


Unkeyed, fast, one-way PRP Are there any fast, secure, one-way, unkeyed almost-pseudorandom permutations? I am looking for something that can hide a MAC, without requiring a secret key and while being much faster than public key crypto.  It is important that it is a almost-PRP, not a PRF.

By "almost-PRP", I mean "a one-to-one function that is also preimage resistant"

There is a misconception here regarding the security of MACs. It is certainly not true that MACs give away the secret key if it is known and the key reused. You are thinking about information-theoretic MACs (or possibly GHASH). However, a secure MAC does not have any problem at all. You can use HMAC or CMAC or even GMAC, and these are secure for many MACs even if the adversary sees many pairs of message/tag (and even if the adversary can choose what messages to get MACed). So, in answer to your question:

It is impossible to have an (almost) pseudorandom permutation without a secret key. You can heuristically use a hash function as a random oracle, but this opens up another big discussion
You do not need such an object for what you want. Just use a normal secure MAC and it is safe.


Do we have to use an IV for AES encryption to be FIPS 140-2 compliant? I asked this question Will our app be FIPS 140-2 compliant if we use our own AES algorithm implementation here before and although there are some different thoughts about this, the general consensus seems to be that our application should be FIPS 140-2 compliant if we use a FIPS certified library.

We are using the AES algorithm from a FIPS certified library — iOS commoncrypto — for the encryption of database and disk files. We generate a key dynamically based on a random salt for each encryption of a file (CBC mode, same key for different block of same file). However, we don't use any initialization vector.

Do we have to use an IV for AES encryption to be FIPS 140-2 compliant?

No you don't need to use an IV. However, this limits you to ECB mode only — the only one which doesn't use an IV — and your CAVP (Cryptographic Algorithm Validation Program) AES certificate will indicate so.


How to reduce Computational Diffie–Hellman problem and Decisional Diffie–Hellman problem to Discrete logarithm problem I'm supposed make some reductions but don't even know where to start. Any help would or explanation on how to do this would be much appreciated.

A reduction here would mean showing that if you had an efficient algorithm A to solve the discrete logarithm problem, then you could use that to construct an efficient algorithm B solving the computational Diffie-Hellman problem. (For starters, assume A always works and construct B that always works. For full credit, given A that works with some probability [over a uniform input], construct a B that works with the same probability [over uniform inputs].)

If you understand what the discrete logarithm and computational Diffie-Hellman problems are, a reduction should be immediate.


Generating DH key with specific bit-length In PKCS#3 the generation for DH secrets mandates to generate them with a minimum size if length is specified:

The central authority may optionally select an integer $\ell$,
the private-value length in bits, that satisfies $2^{\ell-1} \le p$.
[…]
An integer $x$, the private value, shall be generated
privately and randomly. This integer shall satisfy $0 < x < p-1$,
unless the central authority specifies a private-value
length $\ell$, in which case the integer shall satisfy
$2^{\ell-1} \le x < 2^\ell$.

(Math formulas re-typeset in LaTeX for readability; see comments.)
The normal way to do this would be generate a random number over the whole range and loop if it does not fit (pseudo Java):
do {
    x = new BigInteger(lSize, random);
} while(2^(lSize-1) > x || x > 2^lSize || x > p-1); // x.bitLength!=lSize || x > p-1

However this results in looping at least half of the time. Would it be safe to set the most significant bit by hand and generate the rest randomly. I think yes - as the bits are supposed to be independent:
do {
    x = new BigInteger(lSize-1, random);
    x = x.setBit(lSize);
} while (x > p-1);

Is this an acceptable optimization?

Sure thing. You'd lose up to one bit of security, but that's generally acceptable.


Is there a way to know if a cleartext substring is present in a hash? Let's say I have 4 strings - A, B, C & D. I concatenate and hash them in any order: A + B + C + D or A + C + B + D and send it to another party. Let's call this X.

I can also send a hash of A separately to the same party (but cannot send it in plain text). Is there any algorithm that I can use to figure out whether the string A is used while creating X?

Short answer: not really.  I think the closest thing you're going to find is a "cryptographic accumulator." I can accumulate the separate hashes of the strings A,B,C,D.  But even then, testing whether A is in the result requires more than just the accumulator itself - you also needs a piece of data called a "witness for A" - which is a separate number that "proves" that A is in the accumulator.

Merkle trees have the same problem - to prove that A is in the tree, you need more than just the final total of the tree.  You also need to know where A appeared in the tree, and the hashes of the other branches of the tree.


What is a 'secret key factory'? What precisely is it doing? I have found a Java implementation of AES CBC mode that runs in Netbeans. The lines below appear to create the key from password and salt:

SecretKeyFactory factory = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA1");
KeySpec spec = new PBEKeySpec(password.toCharArray(), salt.getBytes(), 65536, 128);
SecretKey tmp = factory.generateSecret(spec);
SecretKey secret = new SecretKeySpec(tmp.getEncoded(), "AES");

The key produced looks strange, here's an example:

secret key : javax.crypto.spec.SecretKeySpec@fffe8a18

I would expect 128 bit key like fffe8a1829ac45ed  If I enter such key of my own making the program crashes.

I would appreciate an idiot's guide as to what is going on.

SecretKeyFactory is a class from the javax.crypto library. This class is used for generating secret symmetric keys. In other words, it generates a SecretKey object from the input key specification (e.g. PBKDF2WithHmacSHA1). Note that your SecretKey instance inherits from java.security.Key which is Serializable and uses a default RAW encoding format.

Hence, you should not just toString() directly. As mentioned by Maeher, there is actually a getEncoded() method which returns the key as a byte array in its primary encoding format for viewing.


Why not send the identity in the encrypted message? I've recently started reading the book "Applied Cryptography" written by Bruce Schneier.

Quite a few times I stumbled across protocols who send the identity outside of the encrypted message (see step 4).

Is there a certain reason to do so? What does speak against sending the identity within the encrypted message?

You can of course add a trusted path requirement to Trent (the trusted key distribution center) on the top of the given protocol. This is however not a requirement for the scheme itself.

Trent, as trusted third party serving multiple users, of course needs to know who to communicate to. So the identity cannot be encrypted with the public key of Alice or Bob.

As you can see the information between Alice and Bob is encrypted. This is no problem as both just use their own key to decrypt the messages between them.

That all said, there seem to be multiple attacks on the scheme - this seems to be one of them. The problem of not establishing a trusted path to the KDC could be a big improvement on the protocol. Just to remind you: only use this protocol for study, not for real life implementations.

Please understand that these protocols are building blocks for creating secure systems. You need to understand exactly what kind of security is provided by the scheme to use it for building a secure system. Anonimity of Alice and Bob when talking to the KDC is clearly not part of the security provided by this protocol.


How is SHA1 different from MD5? On the surface, SHA1 and MD5 look pretty similar. Their diagrams include chunks of bits, bit rotation, xor and special functions. Their implementations are roughly the same length (at least the ones I've seen). Yet it's widely known that MD5 is broken, but currently SHA1 isn't.

Is the security difference from the increased rounds? SHA1 has 80 compared to MD5's 64. Or is it the greater digest size? SHA1 seems to be described as "more conservative", but I'm not sure what that means.

MD5 and SHA-1 have a lot in common; SHA-1 was clearly inspired on either MD5 or MD4, or both (SHA-1 is a patched version of SHA-0, which was published in 1993, while MD5 was described as a RFC in 1992).

The main structural differences are the following:

SHA-1 has a larger state: 160 bits vs 128 bits.
SHA-1 has more rounds: 80 vs 64.
SHA-1 rounds have an extra bit rotation and the mixing of state words is slightly different (mostly to account for the fifth word).
Bitwise combination functions and round constants are different.
Bit rotation counts in SHA-1 are the same for all rounds, while in MD5 each round has its own rotation count.
The message words are pre-processed in SHA-0 and SHA-1. In MD5, each round uses one of the 16 message words "as is"; in SHA-0, the 16 message words are expanded into 80 derived words with a sort of word-wise linear feedback shift register. SHA-1 furthermore adds a bit rotation to these word derivation.

The extra bit rotation is what makes SHA-1 distinct from SHA-0; it also makes SHA-1 much stronger against collision attacks, and, indeed, SHA-0 collisions have been found (with effort $2^{39}$, thus highly doable) while SHA-1 collisions are much more difficult.

We don't have a true theory of what makes a hash function strong. However, we can still have some "gut feelings", and my own intestine tells me that in the case of MD-like functions (MD4, MD5, SHA-0, SHA-1, and the SHA-2 functions), the two important points are:

Rotating bits a lot. Collision attacks based on differential paths try to induce small differences and keep them from propagating non-linearly everywhere; a useful tool for that is the lack of carry beyond the upper bits in word-wise additions (a difference in the upper bit in one of the operands of an addition modulo $2^{32}$ propagates to the output with probability $1$; two such differences cancel each other reliably). The 1-bit rotation added in SHA-1 is effective at making differential paths harder to find.
Doing "enough work". If you count the number of elementary operations per input byte (which more or less translates to code size or speed, especially on GPU), you will see that SHA-1 is about 30% heavier than MD5, while SHA-256 is close to twice heavier than SHA-1. SHA-3 candidates were also, as a rule, "heavier" than SHA-1 (some could get faster by leveraging SIMD opcodes in CPU, but still had more operations per input byte).


Security considerations on "expand 32-byte k"-magic number in the Salsa20 family of stream ciphers? I'm currently examining the NaCl library written by Daniel J. Bernstein and I noticed that the library hard codes the sigma:

static const unsigned char sigma[16] = "expand 32-byte k";

In all the salsa stream implementations:

crypto_stream_xsalsa20
crypto_stream_salsa20
crypto_stream_salsa2012
crypto_stream_salsa208

and the crypto_box library wrapper:

static const unsigned char sigma[16] = "expand 32-byte k";
static const unsigned char n[16] = {0};

int crypto_box_beforenm(
  unsigned char *k,
  const unsigned char *pk,
  const unsigned char *sk
)
{
  unsigned char s[32];
  crypto_scalarmult_curve25519(s,sk,pk);
  return crypto_core_hsalsa20(k,n,s,sigma);
}

As far as I understand from the paper the constant is used to expand the Stream Cipher.

Now:

Why is this variable hardcoded in the library?
Would it make sense to change this magic string to a different value?
Edit: What are the security considerations of using the sigma as provided in the library?

Implementations can be found in the files:

crypto_box/curve25519xsalsa20poly1305/ref/before.c
crypto_stream/salsa2012/ref/xor.c
crypto_stream/salsa2012/ref/stream.c
crypto_stream/salsa20/ref/xor.c
crypto_stream/salsa20/ref/stream.c
crypto_stream/salsa208/ref/xor.c
crypto_stream/salsa208/ref/stream.c
crypto_stream/xsalsa20/ref/xor.c
crypto_stream/xsalsa20/ref/stream.c

Edit: I found the reference to this constant in the paper referenced above as "Salsa20" constant:

  (x0; x5; x10; x15) = (0x61707865; 0x3320646e; 0x79622d32; 0x6b206574);
  in other words, (x0; x5; x10; x15) is the Salsa20 constant.

which is "expand 32-byte k" considering endianness.

Salsa20 has strong rotational symmetry. The main point of these constant is that they're not invariant under rotations, introducing an asymmetry. The precise value isn't very important, as long as it's sufficiently asymmetric.
Bernstein - Salsa20 security says:

Notes on the diagonal constants

Each Salsa20 column round affects each column in the same way starting from
the diagonal. Each Salsa20 row round affects each row in the same way starting
from the diagonal. Consequently, shifting the entire Salsa20 hash-function input
array along the diagonal has exactly the same effect on the output.

The Salsa20 expansion function eliminates this shift structure by limiting the
attacker’s control over the hash-function input. In particular, the input diagonal
is always 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574, which is different
from all its nontrivial shifts. In other words, two distinct arrays with this diagonal
are always in distinct orbits under the shift group.

Similarly, the Salsa20 hash-function operations are almost compatible with
rotation of each input word by, say, 10 bits. Rotation changes the effect of carries
that cross the rotation boundary, but it is consistent with all other carries, and
with the Salsa20 operations other than addition.

The Salsa20 expansion function also eliminates this rotation structure. The
input diagonal is different from all its nontrivial shifts and all its nontrivial
rotations and all nontrivial shifts of its nontrivial rotations. In other words,
two distinct arrays with this diagonal are always in distinct orbits under the
shift/rotate group.

Another relevant document is the somewhat ranty Response to "On the Salsa20 core function".
SipHash shares some design principles with Salsa20 and has a similar constant.  The SipHash paper explains the choice of values:

Choice of constants. The initial state constant corresponds to the ASCII string
“somepseudorandomlygeneratedbytes”, big-endian encoded. There is nothing
special about this value; the only requirement was some asymmetry so that
the initial $v_0$ and $v_1$ differ from $v_2$ and $v_3$. This constant may be set to a “personalization string” but we have not evaluated whether it can safely be chosen as
a “tweak”. Note that two nonzero words of initialization constants would have
been as safe as four.

Would it make sense to change this magic string to a different value?
Keep it unchanged. There might be some rare scenarios where it's useful to customize the constant, but in general you should not.
In response to a question on the CurveCP mailing list, Bernstein wrote:

Is there a recommendation to customise sigma per application ?

No.


Safely use CryptSignAndEncryptMessage? I am developing an application that sends messages which I want to encrypt and sign. The CryptoApi offers a function called CryptSignAndEncryptMessage.
The description says, what this function actually does:

  The CryptSignAndEncryptMessage function creates a hash of the
  specified content, signs the hash, encrypts the content, hashes the
  encrypted contents and the signed hash, and then encodes both the
  encrypted content and the signed hash. The result is the same as if
  the hash were first signed and then encrypted.

If I understood correctly, this solution could be susceptible to an attack called surreptitious forwarding?

Surreptitious forwarding uses the naive "sign and encrypt" approach to allow B to forward a message of A, destined to B, to a third party C and make C think the message was from B, destined to C (although it was from A to B, and just forwarded by B). This is possible because B can decrypt the signed message and re-encrypt it for C.
However, although a message can be forwarded "illegally", the actual message content cannot be changed.

Does this in turn mean, if I include the receiver in the signed data, I am not susceptible to this attack?

If I understood correctly, this solution could be susceptible to an attack called surreptitious forwarding?

If CryptSignAndEncryptMessage is implemented in the naive way, then it would seem that it is vulnerable to a forwarding attack. Microsoft has not published the exact details (AFAIK), so it is difficult to tell for sure.

  Does this in turn mean, if I include the receiver in the signed data, I am not susceptible to this attack?

There is a published recommendation done by a few very respectable cryptographers. It is in Section 7 of On the Security of Joint Signature and Encryption, and is along similar lines to what you propose. Specifically, they recommend:

  Whenever encrypting something, include the identity of the sender $ID_S$ together
  with the encrypted message.
  Whenever signing something, include the identity of the receiver $ID_R$ together with
  the signed message.
  On the receiving side, whenever either the identity of the sender or of the receiver
  do not match what is expected, output $\bot$.


What is the difference between a Vigenère cipher and a one time pad cipher? I'm doing a decryption competition at a nearby college.  We are allowed one cheat sheet so I'm trying to make one.  I realized that the Vigenère cipher was very similar to the one time pad and wanted to make sure that I know the difference.

As I understand it, the only difference is that a one time pad has a key that is as long as the message. The Vigenère cipher can use a key that is shorter than the message, so you repeat the key till the end of the message.

Is above description correct?

The Vigenère cipher is essentially a series of interwoven Caesar ciphers, in which the size of the shift is different for each character and is defined by the keyword.

The one-time pad (OTP) is a very similar technique in which the only difference is that key is generally:

truly random,
at least as long as the message,
and never reused (thus the name),

making it provably confidential if the key is kept secret.

In this way, both ciphers make use of modular addition, which is still in use in most modern digital cryptography. But, in the case of the OTP, the length of the key guarantees that the ciphertext is not vulnerable due to repetition in the way that the Vigenère cipher is.


Why does ROT13 provide no cryptographic security? I can understand that ROT13 is not secure for obvious reasons, but I'm looking for the theoretical answer.  Wikipedia says "The algorithm provides no cryptographic security.."  What does it mean to provide cryptographic security? Why does it provide no security as opposed to, say, very little security?

What would make ROT13 easy to crack from an automated program (e.g. one that had no knowledge at all of what the encryption cipher was)?  How is a cipher measurably "weak?"

I think I understand what you're asking for.  You're trying to learn how we know which algorithm was used, so we know how to attack it.  That's a part of what is known as cryptanalysis, the task of breaking ciphers.

If you are using a standard computer protocol, the encryption algorithm is defined as a part of the protocol.  The computers can't talk unless both know what algorithm is in use.  No attempt is made to keep it secret.

Generally there are plenty of clues will tell you what's going on.  If things are flowing through port 443, the attacker is going to assume it's SSL protocol, look for the header which indicates what algorithms are in use, and begin there.

(If you're reading a joke or a movie plot on-line, ROT-13 has traditionally been used to keep you from accidentally seeing the punchline or spoiler until you're ready.  Thus, ROT-13 is actually a de facto standard.  Note that "standard" does not necessarily mean "secure".)

Even without knowledge of the protocol, though, there are usually other ways to figure out which algorithm was used.  The old school tool is frequency analysis.  The cryptanalyst (the guy whose job is to break the cryptography) might plot out the frequency of characters.  Normal English text follows a distribution such that the letter E appears 12% of the time, T appears 9%, A, O, I, and N appear about 8% each, and so on.  (The nonsense words ETAOIN SHRDLU represent the 12 most common letters in English in descending order.) If the distribution of letters in the ciphertext approximately follows this same distribution, the cryptanalyst can assume a transposition cipher was used to shuffle the plaintext letters.    If a different set of letters follows the same distribution, it's likely that a simple substitution cipher was used.  (ROT-13 follows this pattern, by the way, and can be spotted because the distribution will be RGNBVA FUEQYH.)

If the distribution is flatter, the cryptanalyst might try measuring the distribution for every other letter, or every third letter, or every fourth letter, etc.  If the distribution suddenly follows that same 12,9,8,8,8,8 curve, then the cryptanalyst has discovered that a Vigenere cipher or polyalphabetic cipher might have been used.

Once the algorithm is known, the next task is finding the key.  Frequency analysis can help with the simpler codes, but with the advent of computers a different attack becomes possible.  A computer can quickly try every possible key, which is called a brute-force attack.  The number of keys you would have to try is called the keyspace.  The classical Caesar cipher is a rotation cipher with a key of 3 (shift every letter to the left by 3 places.)  The keyspace of a Caesar cipher is $26^1 - 1$ (there are 26 possible shifts, but cleartext is not considered encrypted), or just 25.  Because these increase exponentially with the number of possible keys, and because brute-forcing is generally done with computers, it's common to refer to these with power of 2 exponent notation. The keysize is generally referred to by the number of bits.  The next power of 2 greater than or equal to 25 is 32, ($32 = 2^5$), so we can say the keysize of a Caesar cipher is 5.

Because the algorithm and key of ROT-13 is known (the algorithm is ROTate, and the key is 13) the keyspace is 1, and the only possible result is to decrypt.  The keysize of ROT13 is $1^{1} = 1$.  The next power of 2 greater than or equal to 1 is $2^0 = 1$.  Therefore the keysize (the exponent) is zero.

Keysize is an upper boundary of cryptographic security for an algorithm, as it represents the number of tries using brute force.  A 40 bit keysize (2^40) is easily brute forced on a home PC.  DES, with a 56 bit key length, was brute forced in the 1990s on a special purpose-built computer (Deep Crack.)  Keysize is an upper boundary only, because if an attacker can figure out a cryptographic weakness in the algorithm, they can use it to reduce the number of brute force attempts.  80 bits is right at the margin of what is considered safe - advances in computer power make brute forcing larger keys more and more possible.

(Please note that this explanation doesn't work the same for RSA keys, where factoring a public key is the method of brute force.  Today, a 1024 bit key is right on the margin of safety, and is not expected to remain safe much longer.)

Cryptanalysis is a fascinating study, and is highly recommended for anyone interested in cryptography.  Being able to break protocols or ciphers is the first step in understanding what is needed to make protocols and ciphers more secure.


Specific discrete logarithm question I came across a DL that I need to solve...

5^k = 6361196924231058595008858273263807320 (mod 15860584089531798358308118294328202587)

The modulus is a 124 bit number, so generic Baby Step - Giant Step would take some $2^{62}$ operations, which is unfeasible on a home PC.

Is there any weakness to it? The modulus is 2 * another huge prime + 1, so definitely not smooth (and susceptible to Pohlig - Hellman).

Apparently, some people solved it on their home PCs in a matter of hours... how? It seems impossible to me.

(12:15) gp > p=15860584089531798358308118294328202587;
(12:15) gp > y=6361196924231058595008858273263807320;
(12:15) gp > x=znlog(Mod(y,p),Mod(5,p))
11473769387225613271575199155876761324
(12:17) gp > ##
  ***   last result computed in 1min, 26,253 ms.
(12:17) gp > Mod(5,p)^x == Mod(y,p)
1
(12:17) gp >
firas@wakaba ~ % cat /proc/cpuinfo |grep 'model name'
model name      : Intel(R) Core(TM) i5-3330 CPU @ 3.00GHz

From the documentation:

  This function uses

  a combination of generic discrete log algorithms (see below).
  in $(\mathbb Z/N\mathbb Z)^*$ when $N$ is prime: a linear sieve index calculus method, suitable for $N < 10^{50}$, say, is used for large prime divisors of the order.

  The generic discrete log algorithms are:

  Pohlig-Hellman algorithm, to reduce to groups of prime order $q$, where $q \mid p-1$ and $p$ is an odd prime divisor of $N$,
  Shanks baby-step/giant-step ($q < 2^{32}$ is small),
  Pollard rho method ($q > 2^{32}$).


The certificate is much more than a public key, changing the public key will of course prevent verification but most of what you did doesn't change that.
Your certificate above also has the following information:
Common Name: INNOPAY
Organization: INNOPAY BV
Organization Unit: Fun Department
Locality: Amsterdam
Country: NL
Valid From: July 24, 2019
Valid To: July 23, 2021
Serial Number: 3838059474068972016 (0x354386c1bab421f0)

changing that may make the certificate invalid and invalidate any signatures on it. but Token verification should be unchanged.


Could we share a secret key using the Birthday problem? I stumbled upon this code on-line, it seems obvious to me that generating all 2^40 keys in trivial time can always be achieved as can hashing each and everyone of them, using the SHARED Salt that "Eve" could easily see:

### Here we outline:
### Sharing a SINGLE FOURTY BIT secret block, using the birthday problem (Proof Of Concept)

Alice (transmit):
MAKE SALT1
SEND SALT1 to Bob
Listen Until:
RECEIVE SALT2 from Bob
Let x = 2^18 (262,144)
Repeat x times:
Generate random 40 bits, call them Kx
Hash(Kx|SALT1) to make Hx
  Tranmit: SEND ALL Hx Values
WAIT FOR BOB'S RESPONSE
If response is:
  (no match found, try again) --> Go back to start
  (maybe match found, Hx, DATA) // If HASH(Kx|SALT2) = DATA, then common key found
  (if still no match found, try again) --> Go back to start
If common key found, respond: "FOUND"|HASH(Kx|SALT2) to Bob to complete confirmation

####################################################################################

Bob (recieve):
MAKE SALT2
SEND SALT2 to Alice
Listen Until:
RECEIVE SALT1 from Alice
Let x = 2^18 (262,144)
Repeat x times:
Generate random 40 bits, call them Kx
Hash(Kx|SALT1) to make Hx
  Wait for: RECEIVE ALL Hx Values
LOOK FOR the first matching calculated and received Hx, if any match
RESPOND EITHER:
       (maybe match found, Hx, HASH(Kx|SALT2) // where multiple matches are found, we use the first match
OR:
       (no match found, try again)
WAIT FOR RESPONSE
  if response reads "FOUND"|{checkable data} then common key found
  if response reads as SALT1, then go back to start

Does this have any practical applications whatsoever? What if the author had suggested that from each 40-bit secret, we use some to produce a salt for verifying Bob and Alice are still talking. Does this "protocol" have any use? Can anyone link where in Bruce Schneier's Applied Cryptography, something like this comes up? It looks familiar but I don't see how it's practical.

You are right that if it costs Alice & Bob effort $N$ to agree on a key in this way, then it costs Eve only effort $N^2$ to find it. So the protocol is not secure in the standard sense, and probably not very useful. (Maybe in some highly constrained situation with very short-lived keys?)

More generally, this purports to be a key agreement protocol whose only ingredient is a hash function / one-way function used in a black-box way. It is known that such a thing is impossible:

  R Impagliazzo, S Rudich, Limits on the Provable Consequences of One-Way Permutations, CRYPTO 1988.


What is the usual block cipher mode that goes with CTS I am wondering: what is the most common, or most used, block cipher mode used that goes with CTS (CypherText Stealing)?

Is it ebc or cbc?

There is a NIST definition of CTS (CipherText Stealing) mode in the addendum to NISTSP800-38A.

The title of that addendum answers the question:

  "Recommendation for Block Cipher Modes of Operation: Three Variants of Ciphertext Stealing for CBC Mode".

The paper is also useful to understand that there are many different ways to do ciphertext stealing.


Block cipher detect padding behaviour Suppose i have a crypto provider, i.e: i give that provider some plaintext bytes and get the encrypted result.
I don't know the used encryption method, but i know it is using a block cipher and the Block cipher mode of operation is something behaving like ECB (every block is encrypted individually => 2 identical blocks of plaintext should lead to 2 identical blocks of ciphertext, if there is no prefix) and thus vulnerable to different padding attacks.
The crypto provider may add a prefix and suffix to the plaintext but i don't know if and how long they are.

I want to execute different padding attacks on this crypto provider (Detect prefix and suffix length, bruteforce suffix in linear time, strip pre- and suffix, ...).
In fact everything works, but i need to know if the padding method used by the crypto provider is appending a padding block if the length of the plaintext % blocksize == 0. Otherwise my calculation of the length of prefix + suffix might be wrong.

Giving the described circumstances, is there a way to detect this without having to test for the exact used padding scheme ?

What i do atm:
To detect the blocksize and prefix + suffix length i start with encrypting one byte, get the length of the cipertext (cipher_a) and then add one byte to the plaintext (plaintext_n) till the length of the cipyertext (cipher_n) is larger as the first one.
Now i know:
blocksize = length(cipher_n) - length(cipher_a)
If the padding used DOES add an empty padding block:
fixes_length = length(cipher_a) - length(plaintext_n)
Otherwise:
fixes_length = length(cipher_a) - length(plaintext_n) -1

Short example which (hopefully) shows the problematic.
Suppose: blocksize = 3, prefix = "xx", suffix = "yy":
With an empty padding block:

 ╔═══════╦═════════════╦═════════╗
 ║ Chars ║ Plaintext   ║ Blocks  ║
 ╠═══════╬═════════════╬═════════╣
 ║ 1     ║ xxa yy-     ║ 2       ║
 ║ 2     ║ xxa ayy --- ║ 3       ║
 ╚═══════╩═════════════╩═════════╝

In this case the calculation is correct.
blocksize = 3
fixes_length = 6 - 2 = 4

Without an empty padding block:

 ╔═══════╦═════════════╦═════════╗
 ║ Chars ║ Plaintext   ║ Blocks  ║
 ╠═══════╬═════════════╬═════════╣
 ║ 1     ║ xxa yy-     ║ 2       ║
 ║ 2     ║ xxa ayy     ║ 2       ║
 ║ 3     ║ xxa aay y-- ║ 3       ║
 ╚═══════╩═════════════╩═════════╝

This fixes_length is wrong.
blocksize = 3
fixes_length = 6 - 3 = 3

I am relatively new to cryptography, so please excuse me if i got some terminology wrong

I am afraid there are no efficient methods of knowing the padding methods deployed unless it is specifically provided by description from whomever authored the original codes. You have to try bruteforcing the padding scheme to estimate what  padding schemes are used.


Computing $g^y\bmod p$ from $g^{y^2}\bmod p$ if Diffie-Hellman is compromised? Given generator $g$ of a multiplicative group mod a prime $p$ the Diffie Hellman problem is to find $$g^{xy}\bmod p$$ from $g^x\bmod p$ and $g^y\bmod p$. The best way to solve this is through discrete logarithms. Assume we can do this without breaking discrete logarithms.
Then is computing $g^z\bmod p$ from $g^{z^2}\bmod p$ doable in polynomial time?

Then is computing $g^z\bmod p$ from $g^{z^2}\bmod p$ doable in polynomial time?

If we assume that we know the order $q$ of $g$, and that it is prime, then yes, it is feasible.
Then, we can treat members of this subgroup as an abstract group, where each member is $g^a$ for some $a$.  Within this abstract group, we can perform multiplication with the Oracle, that is, given $g^a$ and $g^b$, we can compute $g^{ab \bmod q}$.  By extension, we can perform exponentiation in polynomial time, that is, given $g^a$ and an integer $c$, we can compute $g^{a^c \bmod q}$.  And, we can compute the additive inverse (given $g^a$, we can compute $g^{-a \bmod q}$)
We further have an equality operator on this group, that is, given $g^a$ and $g^b$, we can determine whether $a \equiv b \pmod q$).
These operations are sufficient to implement the Tonelli-Shanks algorithm within the abstract group; this allows us to compute square-roots in polynomial time [1], and specifically, given $g^{z^2}$, to recover the two square root elements $g^z$ and $g^{-z}$

[1]: Probabilistic polynomial time if $q \equiv 1 \pmod 4$; however the probabilistic step is to find a quadratic nonresidue, and that needs to be done only once for a specific group.


How to extract MAC and AES keys using x9.63 based kdf For trying ECIES, I need to derive keys for MAC and AES from the shared secret using ANSI x9.63 based KDF. The information on key derivation I got it from Section 3.6.1 of http://www.secg.org/sec1-v2.pdf.

What is the standard procedure to extract/separate the keys for MAC and AES from the Key derived using KDF?

For that standard, it is covered in Section 5.1.3:

  Use the key derivation function KDF established during the setup procedure to generate keying data K of length enckeylen + mackeylen
  octets from Z and [SharedInfo1 ]. If the key derivation function
  outputs “invalid”, output “invalid” and stop.
  Parse the leftmost enckeylen octets of K as an encryption key EK and the rightmost mackeylen octets of K as a MAC key MK. If symmetric
  encryption method is XOR and backwards compatibility mode is not
  selected, then instead parse the rightmost enckeylen octets of K as an
  encryption key EK and the leftmost mackeylen octets of K as a MAC key
  MK.

In the end, it depends on the parameters enckeylen and mackeylen, which define the sizes of the keys for the symmetric encryption and the MAC, respectively.


what is the difference between IBE and ABE schemes Can somebody explain in simple words. real life example light help and limitations of these schemes etc.

With IBE the public key is a public bitstring as your email. A Key-authority issues a secret key that is tied with this public key.The owner of the secret key can only decrypt.

ABE entails more complex access control on decryption operation such as:"Only the owner of the secret key that corresponds to: Area:=Italy AND Age:<30 and Business:=Researcher" can decrypt. The last predicates are called the attributes


Detect MITM with hashed session-key — Is my protocol secure? I have the following setup:
An app ("client") wants to communicate securely with a device I created ("server").
The client has the public key of the server (and a hashed password) preinstalled.

I use the libhydrogen crypto library (inspired by libsodium / same creator as libsodium).

First, I do a key exchange (using the N variant) to generate my session key.
Then I use secret-key authenticated encryption for my communication.

As far as I know, I'm still vulnerable to MITM attacks because the key exchange does not protect me from that.
To check if there is a MITM I would like to compare if both parties have the same symmetric session key.

Q1: If I am able to compare that the session keys and they are the same, can I assume that the connection is secure (no MITM present)?

In order to do that comparison, my idea is to send a packet containing a hash of the session key + a hashed password from the client to the server. This packet will be encrypted using the public key of the server.

 This means that only the server is able to decripty the message and will be able to verify that they use the same session key (+ I can use that to authorize the client). Because of the password, a MITM will not be able to create the same message with his false session key.

Q2: Are my assumptions correct or did I miss something?

Q3: Could I do the whole thing simpler or am I on the right track? (If I do not want to use TLS)

If I am able to compare that the session keys and they are the same, can I assume that the connection is secure (no MITM present)?

Yes, baring attack on the extremities. That's a property of the Diffie-Hellman key exchange.

However, it is not satisfactory that the client sends (as envisioned) $\text{ENC}_\text{PK}(\text{Hash}(\text{Sym.Session Key})\mathbin\|\text{Hash}(\text{Password}))$ (without using further encryption with the session key) in order to check that the two ends share the same session key. The security depends on details of the public key encryption used. For example, in some forms of RSA encryption, we would have what's sent equal to $\text{ENC}_\text{PK}(\text{Hash}(\text{Sym.Session Key}))\mathbin\|\text{ENC}_\text{PK}(\text{Hash}(\text{Password}))$, the right term could be extracted by mere passive eavesdropping, then allowing that attacker to authenticate w.r.t. the server.

Also, there's the issue that libhydrogen does not seem to offer public key encryption (at least glancing at the table of content).

The simplest working solution is to send $\text{Hash}(\text{Password})$ within the secret-key authenticated encryption channel, as the first payload, and have the server decipher and check that against the correct value.

A convincing security argument (not proof) that the above is enough for security is that

In a MitM attack modifying what's exchanged before the packet carrying the above payload, an attacker can't impersonate the server w.r.t. the client. The client will abort before anything related to $\text{Hash}(\text{Password})$ is sent.
In an attack (passive or active) starting after that, the attacker has no knowledge of the session key, and that key won't be reused in another session. Hence whatever the adversary intercepts that depends on $\text{Hash}(\text{Password})$ does not leak information about that; and (independently) is of no use in later sessions.
The use of correct authenticated encryption should take care of ensuring that whatever the adversary intercepts that depends on $\text{Hash}(\text{Password})$ is of no use in the current session (in particular, it is necessary that individually authenticated packets can't be replayed; if they could, replay of the packet with $\text{Hash}(\text{Password})$ in the right context could leak information about its plaintext).

However, the above simplest working solution is a tad brittle: if the server's private key leaks, an attacker impersonating the server w.r.t. a client can obtain the hash of the password (which is as good as the password for authentication purposes). And if a session keys leaks, passive eavesdropping allows the same.

Rather (and following the reasoning in the first part), we could send some MAC with key $\text{Hash}(\text{Password})$ and message $\text{Sym.Session Key}$, which the server can check. HMAC-SHA-256 would be suitable. There's an important incentive to further send that MAC thru the secret-key authenticated encryption channel: it prevents an adversary from checking a guess of the password unless s/he has the server's private key.

Note: If password is to be short enough to be conveniently keyed-in, or otherwise low-entropy, then $\text{Hash}(\text{Password})$ should still preferably be with a slow hash intended for passwords.

Note: No matter what, the password should have enough entropy to resist online password guesses, where an adversary attempts to authenticate w.r.t. the server using a dictionary of passwords. Limitation of the number of invalid attempts on the server (perhaps by a mere delay) can help with this.


Does Schnorr's 2021 factoring method show that the RSA cryptosystem is not secure? Claus Peter Schnorr recently posted a 12-page factoring method by SVP algorithms. Is it correct?
It says that the algorithm factors integers $N \approx 2^{400}$ and $N \approx 2^{800}$ by $4.2 \cdot 10^{9}$ and $8.4 \cdot 10^{10}$ arithmetic operations.
Does this lead to the conclusion that the RSA cryptosystem is no longer secure in some sense?

Moderator note: a fourth version dated 2021-04-08 has appeared; this is pretty normal for eprint. It seems settled Claus Peter Schnorr (of Schnorr group and Schnorr signature fame) intends pre-publication of this paper, including abstract as on eprint.

No.
If the claim was true, then there would be an extremely simple way to prove it: $10^{10}$ arithmetic operations is nothing. There are tons of 800-bit factoring challenges available online. The author could just solve them and include the factorization in the submission; the lack of such a straightforward validation should be taken as empirical evidence that the claim is, as of today, unsubstantiated at best.
Leo Ducas, one of the top experts in lattice-based cryptography (and especially in its cryptanalysis) has implemented the March 3 version of the paper. The preliminary experimental evaluations seem to indicate that the method cannot outperform the state of the art (quoted from here):

This suggest that the approach may be sensible, but that not all short vectors give rise to factoring relations, and that obtaining a sufficient success rate requires much larger lattice dimension than claimed in [Sch21].

Personnal study (unfortunately, never written down cleanly) of this approach suggested me that this approach requires solving SVP in dimensions beyond reasonable, leading to a factorization algorithm much slower than the state of the art. My impression is that this is the consensus among experts having spent some time on it as well.

The corresponding Twitter thread is here.
Furthermore, this Twitter thread points to what seems to be a fatal mistake in Schnorr's paper.
(Warning: personal view) I'm also basing my conclusion on the fact that several top experts on SVP and CVP algorithms have looked at the paper and concluded that it is incorrect (I cannot provide names, since it was in the context of anonymous reviews). Of course, the latter should not be treated as clear evidence, since I'm not providing proof of this statement - please treat it simply as it is, a claim I'm making.
(This statement refers to the version of the paper which was initially uploaded, and whose eprint extracted abstract  contained a claim that RSA was "destroyed", together with the sample running times given in OP's question. Schnorr himself still claimed, after being asked by mail about the paper, that the latest version breaks RSA - and so does its abstract; with respect to this claim and given the lack of solved RSA challenge, I stand by my statement that it should be regarded as essentially unsubstantiated).
Among the potential issues (again to be treated with care, as pointers to help people willing to look further into where the paper might fail):

The proof of (5.8) does only show the existence of many smooth triples, but says nothing about the probability of successfully finding factoring relations.
The paper relies on the Schnorr-Hörner pruning strategy, which is known to be flawed.
No justification is given for the cost indicated for (3.2)


How reassuring is CRC-then-XTS as authenticated encryption? It is known that the "xz" compression format embeds a checksum in the compressed file to verify integrity during decompression or standalone testing. The algorithm of the checksum can be one of: CRC32, CRC64, and SHA256, and the default is CRC64.

Now, we put an "xz" file into a XTS-encrypted disk image. The XTS mode is a pure confidentiality mode, and have no authenticity or integrity feature at all. But the "xz" file inside it has integrity feature. So the question is:

When combining the CRC64 integrity of "xz" with the confidentiality of XTS mode of operation, do we get a secure deterministic authenticated encryption (DAE, a.k.a. key-wrap) scheme?

No, this does not make a deterministic authenticated cipher, unless you're using a secret CRC as a MAC.

How do you break it?  First, find a pair of messages $m = m_1 \mathbin\| m_2$ and $m' = m'_1 \mathbin\| m'_2$ so that $m_i \ne m'_i$ and $\operatorname{CRC}(m) = \operatorname{CRC}(m')$.  (Finding collisions in CRCs is not hard.)  Then:

Query the oracle for $m_1 \mathbin\| m_2$ to find the ciphertext $c_1 \mathbin\| c_2 \mathbin\| c_3$; assume the CRC is in the plaintext of block $c_3$.
Query the oracle for $m'_1 \mathbin\| m_2$ to find the ciphertext $c'_1 \mathbin\| c_2 \mathbin\| c_{\mathit{garbage}}$.
Query the oracle for $m_1 \mathbin\| m'_2$ to find the ciphertext $c_1 \mathbin\| c'_2 \mathbin\| c_{\mathit{garbage}}$.

Finally, yield $c'_1 \mathbin\| c'_2 \mathbin\| c_3$ as a forgery, for the message $m'_1 \mathbin\| m'_2$ not previously sent to the oracle.


Password Entropy in bits for passwords of a certain structure I have read this post and this post about how best to calculate a pseudo accurate entropy in bits of a password.
I can do this fine for passwords of a uniform nature, such as 8 letters of an a-z range is:
26(a-z)^8(length) = 208,827,064,576

Then to bits:
log2 (208,827,064,576) = 37.6035177451 = 38,

So it's guassable entropy S is 38 - 1  = 37 bits.
My problem:
Now, I have a password made up of the following structure:
A-z, 0-9, a-z, 0-9 .... to ten characters long (5 of each type).

Example:

A9B8C7D6E5

I figure the entropy value of that would be:
(b): 26 * 10 * 26 * 10 * 26 * 10 * 26 * 10 * 26 * 10 = 1,188,137,600,000

I had tried other variations for shorter syntax such as (26 * 10)^5 but these figures didn't seem to corellate.
Anyhow the above gives entropy bits of:
   log2(1.1881376e+12) = 40.1118390651

So S is 40. This strikes me as being only a tiny bit larger than the first example, and I think I'm working this correctly, and I am aware the numeric characters do severely limit the potential entropy of the whole password.

Is my caculation and conclusion (S~40) correct?

If so; is there a more efficient way of working out equation (b)?

Thanks.

Is my caculation and conclusion (S~40) correct?

Yes, but it's important to state the premises behind these calculations and not relegate them to a footnote.  Namely, that each character in the password is selected uniformly at random, independently of every other one.  We routinely see people talk about password "entropy" in contexts where passwords are evidently not being selected randomly.  And in such contexts your calculation doesn't tell you anything about the password's security.

Keep in mind also that overwhelmingly most people don't select passwords randomly.  These numbers apply in circumstances that are, in real life, exceptional.

  If so; is there a more efficient way of working out equation (b)?

Yes, by using the laws of logarithms, which allow you to work it out by adding small numbers instead of multiplying huge ones:

$$
\log(n \times m) = \log(n) + \log(m)
$$

This is why entropy is normally expressed in bits—the base 2 logarithm of the number of equiprobable alternatives—because it just makes the math much easier.  In this case:

The uniform random choice of one character out of a set of 26 is $\log_2(26) \approx 4.7$ bits.
The uniform random choice of one character out of a set of 10 is $\log_2(10) \approx 3.3$ bits.
The entropy of a sequence of independent random choices is the sum of their individual entropies.

Therefore, a randomly generated eight letter password has entropy of about $8 \times 4.7 = 37.6$ bits, and one randomly generated according to your latter schema has approximately $5 \times 4.7 + 5 \times 3.3 = 5 \times 8 = 40$ bits of entropy.

Addressing this comment:

  @CodesInChaos your comment seems to imply that the order of certain character sets doesn't seem to matter when calculating entropy. I was wary of making this assumption myself when facing potential solutions to this problem.

If the order is predetermined then it doesn't matter, because then there's no choice about the order, therefore no uncertainty.  Another way of looking at this is that there's a bijective function between the set of passwords that look like ABCDE12345 and A1B2C3D4E5, so therefore the uniform random choice of an element out of one set must have the same entropy as from the other.  (The entropy is the base 2 logarithm of the number of alternatives in the uniform case, and in both cases the total number of alternatives is the same.)


How to propagate error in variable-sized message? I want to design a scheme to encrypt a variable-length message with a secret key, to provide confidentiality. The message is a short human-readable text string with byte granularity, let's say under 300 bytes. I prefer that the ciphertext is the same length as the plaintext (avoid padding).

Along the way, I also want to support integrity-checking on a best-effort basis. Preferably, I want it so that if any bit of the ciphertext is changed, then the decrypted plaintext will look garbled. (The decrypted output will actually be read by a human, and no automated checking is needed.)

It is not acceptable to append a MAC or any kind of check code due to message size restrictions; valid decryption must be inferred from the garbling of the message itself. CPU time is not a problem as long as it's under 0.1 second. An inefficient but secure scheme is okay, but the scheme should be conceptually simple to describe/audit/implement.

The complicating factor is that the message may be shorter than a block (say 16 bytes, for the AES cipher), which means ciphertext stealing can't be used. (Right?)

I'm aware of these facts already:

Using a stream cipher satisfies the variable-length property but makes the ciphertext very malleable; this is undesirable.
Using a block cipher gives the "decryption garble" property desired.
Using CBC mode instead of ECB will mask repeating patterns in the input.
Ciphertext stealing (for ECB or CBC) makes it possible to not increase the message length - but only if the message is at least one block long.
It's possible to use a keyed hash function / MAC for 3 or 4 rounds to design a custom Feistel network cipher.
It might be possible to use a stream cipher and a bytewise adaptation of the Infinite Garble Extension (IGE) mode to achieve garble propagation.
Designing "home-made" crypto not reviewed by experts is frowned upon and may have subtle and fatal errors.

But I don't know what else I need to know, and how to proceed from here. I can post more details on some of the proposed algorithms (such as IGE and Feistel) if needed.

Addendum:

Feistel network idea: (using Python pseudocode)

Let H(k, m) be a MAC (such as HMAC-SHA-512) with secret key k.
Let M be the message to be encrypted.
Let i = floor(M.length / 2).

Algorithm:
M[0 : i] ^= truncate(H(k, M[i : M.length]))  # left half XOR H(right half)
M[i : M.length] ^= truncate(H(k, M[0 : i]))  # right half XOR H(left half)
M[0 : i] ^= truncate(H(k, M[i : M.length]))  # Round 3 to achieve error propagation
M[i : M.length] ^= truncate(H(k, M[0 : i]))  # Round 4 due to recommendations

(If half the message length is less than the MAC/hash length then truncating is easy. But if it's longer then some kind of stretching, i.e. CSPRNG, is needed.)

Second addendum:

I'm leaning towards this solution:

preprocessed = all-or-nothing-transform(message)
ciphertext = preprocessed XOR (stream cipher keystream)

The scenario you're facing is well-known in cryptography. You can't afford expanding the message at all (maybe by some IV). So you can't get strong authentication but have to rely on what is called poor man's authentication, you rely on tampering causing random messages.

Please note that all of the following modes are somewhat block-based, meaning you'd have to use padding (like PKCS#7) to ensure correctness of the data and you have to actually check the padding to protect against POODLE style attacks.

The exact same scenario is given in the full-disk-encryption (FDE) scenario. This gives you four options, plus those added by other answers.

XTS, the standard mode for full-disk encryption. It allows for two tweaks hiding potential patterns. You can use standard padding methods (PKCS#7) if you're not hitting block boundaries, this is the most standard solution but may not scramble enough as it only affects the current block.
PCBC is a mode that propagates errors infinitely into the following decrypted plain texts. It accepts IVs and also hides patterns. This may not be preferable compared to the all-or-nothing transforms but may be the choice if they're too slow. And you may want to avoid this one if possible to not fall against the "same flip attack"  although this would still mean that two blocks (32 bytes for AES) are scrambled.
EME, a mode originally specifically designed for full-disk encryption and tackling the poor man's authentication best. It turns every block cipher with block size $n$ into a larger block cipher with block size $n^2$ and accepts tweaks to hide patterns and provide random-access. If you'd use AES this would mean you can encrypt up to 2048 ($=128^2/8$) bytes and make sure the whole block is scrambled if tampered. The main drawbacks are potential patents and the lower speed of requriring double the amount of block cipher calls and a finite field multiplication. EME may not be a good choice if patent-freeness is required.
All or nothing transforms. You can use standard XTS or something like that, but apply an all-or-nothing transform on the plain text to make sure the receiver has the complete and correct set of all blocks. This is somewhat non-standard but looks like the best solution.


What is the purpose of placing the most significant byte first? When the SHA algorithm states "A block of 128 bits is appended to the message. This block is treated as an unsigned 128-bit integer (most significant byte first) [emphasis added] and contains the length of the original message (before the padding)[,]" what is the purpose of placing the most significant byte first?

For example, if we have an integer of 24, which would be 00011000, and we therefore need 15 bytes of 0's to complete our 128-bit block, does this mean that 00011000 comes first followed by 15 bytes of 0's? It seems like this must be what they're saying.

I'm just confused why this byte needs to be first...

Source: Network Security Essentials (6th ed), William Stallings, p. 72

$24$ expressed as a 16-byte hexadecimal number is
$$00\;00\;00\;00\;00\;00\;00\;00\;00\;00\;00\;00\;00\;00\;00\;18$$
The most significant byte is the leftmost. $00011000_2$ comes last, not first.

It makes no difference to the security of the algorithm whether the most significant byte comes first or last. What is important is that everybody agrees on this point.


Is there a hash function with 2048bit output? Is there a publicly available cryptographic hashing algorithm with 2048 bit output?

The standard ones are "only" up to 512 bit (SHA-512, WHIRLPOOL).

(2048 bits are 256 bytes, so it would be useful for generating a full-length key for the ARC4 cipher)

I was already wondering why you would need 2048 bits, because brute forcing a 512 bit output hash takes already a $2^{256}$ operations on average (w.r.t to collision resistance, due to the Birthday Paradox – preimage and second-preimage attacks take on average $2^{511}$ hashes), which is secure enough, for all kinds of hardware available today.

I assumed that you would probably want to transform the hash output into some form of key with a length of 2048 bits, your comment confirmed this. In that case, what you need is not necessarily a hash output of that length, but you need a secure Key Derivation Function (KDF) that allows "stretching" the random hash output to the desired size.

Have a look for example at the KDF described in NIST Special Publication 800-56A: “Recommendation for Pair-Wise
Key Establishment Schemes
Using Discrete Logarithm
Cryptography ” that describes how to stretch hash outputs to arbitrary sizes securely.

When equipped with such a KDF, it basically doesn't matter what hash function you are using (as long as it itself is secure) so you can safely use one of the sha-2 family hashes (SHA-256, 512 etc.).


Is authenticated encryption basically a lockable box? I recently used a custom construction as a commitment scheme, which was taken from the standard picture you give people while explaining commitment schemes.

Basically commitment schemes can be described in terms of physical objects, as "put the information to commit to in a lockable box, give the other person the box and keep the key. As soon as you want to prove that you had the information at the previous time, give him the key to verify".

Now Schneier (in Applied Cryptography 2nd edition p. 86) describes a block cipher based commitment following the exact same principle (with block ciphers). Choose some random value (B does) and let A encrypt it using the key to which A wants to commit, basically exchanging "key" and "content".

Now for the custom scheme:

Suppose you are using an authenticated encryption scheme (e.g. AES-GCM) and you want to commit to a value $R$.

Encrypt $R$ using a randomly chosen $k$ and choose a random IV and append the tag. ($=IV||C||tag$)
Send $k$ to the verifier at the point of verification.

So the question:
Is authenticated encryption the computer equivalent to a lockable box (in this context)? or equivalently: Can the above commitment scheme be broken (and if yes, how?)

For me it looks like the above question is equivalent to:
Given a ciphertext with tag, there's only one key that will produce the correct tag with the given ciphertext, meaning the corresponding plaintext can't be altered.

No.

Yes, by choosing an authenticated encryption scheme with a known $\:I\hspace{.03 in}V\hspace{.04 in}||\hspace{.04 in}C\hspace{.04 in}||\hspace{.04 in}tag\:$ and $k_{\hspace{.02 in}0}$ and $k_1$ such that decrypting $\:I\hspace{.03 in}V\hspace{.04 in}||\hspace{.04 in}C\hspace{.04 in}||\hspace{.04 in}tag\:$ with $k_{\hspace{.02 in}0}$ and $k_1$ yields different outputs, neither of which are $\perp$.

These three links describe a black-box construction of authenticated encryption from one-way functions. $\:$ On the other hand, there is no known construction of non-interactive commitments from one-way functions, and this paper declares, "We rule out the possibility of black-box constructions of non-interactive commitments from general (possibly not one-to-one) one-way functions." However, Naor's scheme comes close.

The only candidate constructions of non-interactive commitments that I'm aware of either use a

$\:$ (1) key agreement scheme with sufficient completeness (this is the standard way to do it), or
$\;\;\;\;$
$\:$ (2) family of injections given by tuples of multi-variate polynomials over finite fields, or a
$\;\;\;\;$
$\:$ (3) keyless CRHF (these cannot be secure against non-uniform committers), or a
$\;\;\;\;$
$\:$ (4) hitting one-way function (in addition to presumably being only computationally hiding,

$\:$ these are also not known to be binding against (uniform) efficient committers)

.


Changing encryption key without revealing the original key Say that Alice encrypts a $\text{plaintext}$ with $\text{key}_{m}$ and gives the $\text{ciphertext}_m$ to Bob. Alice wants to send several gigabytes of $\text{plaintext}$ to Eve but she is on a mobile 3G connection. So instead, Alice and Eve exchange a new secret $\text{key}_{eve}$. She then creates a $\text{key}_{mutate} = \operatorname{Keymutate}(\text{key}_m, \text{key}_{eve})$ and sends it Bob where he applies a mutation function to produce $\text{ciphertext}_{eve} = \operatorname{Mutate}(\text{ciphertext}_m, \text{key}_{mutate})$. Bob sends the $\text{ciphertext}_{eve}$ to Eve and she produces the $\text{plaintext} = \operatorname{Decrypt}(\text{ciphertext}_{eve}, \text{key}_{eve})$.

This seems like a homomorphic encryption cryptosystem, does something like this possible or even implemented?

As CodesInChaos already answered in the comments, this seems to be a perfect fit for proxy re-encryption (PRE). The basic idea of PRE is that a ciphertext encrypted under the public key of user $A$ can be transformed (i.e., re-encrypted) into a ciphertext decryptable by the private key of user $B$; the re-encryption process does not reveal any information about the underlying message.

Note then that proxy re-encryption is a type of public-key encryption. Therefore, users in your scenario should have pairs of public and private keys. Proxy re-encryption schemes come in all flavors (unidirectional vs. bidirectional, single-use vs. multi-use, interactive vs. non-interactive, etc.). Depending on your scenario, you would choose one or another.

However, from your question, one could think that users were using symmetric encryption. In case you were asking for the symmetric counterpart of PRE, then this can be constructed using other mechanisms, such as Key-Homomorphic Pseudo-Random Functions.