Can I jettison MAC if I already have SHA1(M)?

The short answer: No.  It is not secure.

Details. To answer the question properly, we first have to decide what we mean by "secure".  In this case, I assume security means confidentiality plus integrity.  So let's talk about each separately.

Integrity: yes, this provides integrity, under your assumptions.  @poncho explained why.
Confidentiality: no, this does not provide strong confidentiality protection.  There are chosen-ciphertext attacks that may allow an active attacker to learn partial information about M.

The details and feasibility of such an attack will depend upon things like exactly what padding scheme you use, whether known plaintext is available, and so on.  However, the basic concept is: the attacker replaces Bob's transmission with a carefully constructed ciphertext, and watches Alice's reaction.  In many systems, Alice's reaction will reveal whether the decrypted message matched Alice's hash.  Thus, the attacker learns 1 bit of information from Alice's reaction.  And, in certain situations, an attacker can leverage this to learn partial information about M, by choosing his ciphertext cleverly.

Read about padding oracle attacks and that sort of thing to learn more.

Summary. Use a message authentication code in encrypt-then-authenticate mode, or use authenticated encryption.  This stuff is tricky and subtle.  Don't try to take shortcuts.  It is too easy to open up a non-obvious security weakness.

More details: (added 7/29) I see some folks don't believe that the confidentiality attacks are possible.  The misplaced confidence in the impossibility of such attacks is an interesting comment on how people's convictions about what is secure are not necessarily correlated to what is actually secure, but I guess I should give further references to demonstrate the possibility of such attacks, as they are non-obvious, counter-intuitive, and quite surprising.  To learn more, see, e.g.,

Attacking the IPsec Standards in Encryption-only Configurations, Jean Paul Degabriele and Kenneth G. Paterson, IEEE Security and Privacy 2007.
Problem areas for the IP security protocols, Steven M. Bellovin, Usenix Security 1996, Section 3.8.
Password Interception in a SSL/TLS Channel, Brice Canvel et al, CRYPTO 2003.
Intercepting Mobile Communications: The Insecurity of 802.11, Nikita Borisov et al, MOBICOM 2001, Sections 4.4.2, 4.5.

Pro tip: you might want to make sure you understand the attacks in those papers before feeling too confident that the scheme proposed here can definitely resist those kinds of attacks.

An example attack: For those who have read the papers, here's a sketch of an example attack against the scheme proposed here.

Let's make some assumptions to keep the example simple.  Suppose that, before encryption, the message M is padded out to a multiple of 16 bytes by appending arbitrary bytes and then a single byte indicating how many bytes of padding should be removed.  Suppose for simplicity of exposition that the message M is always exactly 1 byte long.  This means M will be padded before encryption out to 16 bytes by appending 14 random bytes and then 1 byte with the value 0x0F.  Suppose that the attacker has previously captured plenty of known plaintext and its corresponding encryption, and now the attacker has intercepted the encryption of M and wants to learn something about M.

Now, suppose the attacker has a guess G at the value of the message (G is a single byte), and the attacker wants to confirm whether M=G or not.  Here's how the attacker can confirm his guess.

Let $IV$ denote the IV used when encrypting M; note that $IV$ is known to the attacker.  The attacker looks through his collection of pairs $(P_i,C_i)$ of known input-output pairs for AES (each one is a block width); these can be derived from the known plaintext and ciphertext for a CBC-mode encryption.  The attacker looks for such a pair $(P_i,C_i)$ such that $IV \oplus P_i$ has G as its first byte and has 0xF as its last byte.  The attacker replaces the ciphertext that Bob sent by the ciphertext $(IV, C_i)$ and waits to see Alice's reaction.  If Alice rejects this message, then the attacker learns that $M\ne G$.  If Alice accepts this message, the attacker learns that $M=G$.

Therefore, the possibility of this attack means that the scheme proposed in this question does not provide semantic security: it is not IND-CCA2 secure.  Put in non-technical terms, it does not provide the level of confidentiality protection that we have come to expect from an encryption scheme.  In practice, such a vulnerability might be quite severe and might be readily exploitable by bad guys.

If you've read the research literature that I cited above, none of this is anything especially novel or new.  Of course, if you're not familiar with that research literature, this stuff is thoroughly surprising and unexpected.  So, take this as a lesson about the dangers of departing from accepted practice, even if everything seems fine to you.  If you're not an expert in this area, you probably aren't qualified to judge whether your scheme is secure -- and if you are an expert, I suspect you'll probably be especially leary of departing from accepted practice, given the number of surprising attacks that have been discovered in the past.


How to use AES correctly in BPS Format Preserving Encryption

AES is directly used as a block cipher without a mode of operation in BC / BPS.

This would be identical to ECB mode for one block or CBC mode for one block and a zero IV in the case that the block cipher itself is not directly available. In that case you should not pad or remove a full block of padding if padding cannot be avoided. CTR of one block with a zero IV/nonce would also work.

But basically the answer to "what modes are acceptable" is: none. In that case the IV is also not applicable. The tweak can be seen as a specific kind of IV. Likewise you could see BC itself as a mode of operation for the block cipher.


How is EdDSA different from ECDSA with a custom curve?

EdDSA is not ECDSA over a different curve. Rather, it is a type of Schnorr signature. Indeed the name is very confusing, and I'm pretty sure that it was chosen in order to give this impression, since Schnorr is less well known.
Schnorr is essentially a zero-knowledge proof of knowledge of the discrete log of the public key, obtained via the Fiat-Shamir paradigm applied to the classic Schnorr Sigma protocol.
ECDSA is a completely different signature scheme, which was designed specifically to bypass Schnorr's patent (at least, this is the understanding in the field).


As bmm60 comments, its not clear that the entropy has gone down. There are many forms of encryption that still preserve some level of information about the input (the encrypted version of a bitmap under a block cipher using ECB is a good example). It's also possible that your encryption product adds unencrypted metadata to a file and if there's a large amount of metadata relative to the file size and the metadata is of a very stereotyped form (such as English readable ASCII) then this will have less entropy than the pdf format.
Without more detail on the input and encryption method, there is a limit to what can be said.
UPDATE: According to the description of PDF encryption in this Black Hat talk 256-bit AES-CBC is used. For lengthy plaintexts this should remove bytewise structure and the bytewise entropy should tend towards 8-bits for larger texts. However, the talk also says that PDF encryption only encrypts some of the objects in PDF's Carousel Object Structure and the other objects are unencrypted, largely human readable, markup language which might have a bytewise entropy of only 4-5 bits (English language words have a bytewise entropy in this range). Therefore if the input file is quite short or has a lot of object structures that are neither stream nor strings, the entropy will be closer to this figure. For pdfs with more pages (and hence larger string and streams sections) the entropy should be closer to 8-bits.
Thanks to kelalaka for pointing out the Black Hat talk.


First, you should not use $p-1$ as modulus. Instead , use a big prime factor $q$ of $p-1$, as it is done in the DSA algorithm.

The DSA variant  you describe exists as an elliptic curve version. It is called EC-GDSA ( Elliptic Curve German Digital Signature Algorithm) . It is described here: https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TR03111/BSI-TR-03111_pdf.pdf?__blob=publicationFile


When did Kerckhoffs's principle become fully accepted in design and practice of modern ciphers?

As I noted in another answer, Auguste Kerckhoffs published his principles in the scientific/academic journal “Journal des sciences militaires, vol. IX, pp. 5–38 in his article "II. DESIDERATA DE LA CRYPTOGRAPHIE MILITAIRE.", Jan. 1883.

So, when you ask since when academics and cryptographers “might” have been accepting (and even applying) those rules, the answer would be: Since the publication of those principles in a scientific journal in 1883, while they gradually gained importance and acceptance during the past 132 years.

Yet, that might be a bit too short and easy as an answer… so let’s dive into some more detail.

From my personal point of view, the statement

  …at some point, cryptographers in general "got it"…

is wrong for two reasons:

As with most innovations and/or publications, “general acceptance” is something which is hard to pin-point. When it comes to Kerckhoffs principles, this is something that happened over time.

It should be remembered that Kerckhoffs was a Dutch linguist, cryptographer, and professor of languages at the École des Hautes Études Commerciales in Paris at the beginning of the 19th century.

Back in his days, “education” was not accessible as it is today and not many of his (more commercially interested) students focussed on cryptography. One could almost say that, generally, people didn’t care about cryptography in a way we do today. So – at first – Kerckhoffs principles were more of military and (limited) academical interest, but not general interest.

There was no point in time where cryptographers suddenly “got it”.

What can be observed is that – while time progressed – people who were involved with cryptography slowly but steadily started to recognize the importance of Kerckhoffs publication.

What can also be observed, is how – at the same time – the cryptographic community slowly shifted from a minority of military strategists and academically interested people, to a rather broad, general public (as we nowadays call it).

Yet, all that spans the past 132 years!

For example: when you dive into crypto-history, you will discover that there are examples of WWI cryptography that actively respected most of his principles.

Same goes for WWII cryptography… even though the most famous WWII crypto device – the Enigma – is a prime counter-example which shows what happens if you ignore Kerckhoffs advice. Nevertheless, we shouldn’t ignore the influence of both world wars in this context.

Also, factors like the electronic revolution, up to the invention of a world wide network we now call “the internet”, definitely added to the general acceptance of some of Kerckhoffs principles (especially, the 2nd one).

No matter which individual influence we pick, they all point at a simple fact: there was no “ugh, Kerckhoffs was correct so let’s all follow his principle(s)” moment in history. Instead, there were several independent points in history which added to the acceptance of his publication and the general acknowledgement of his (eg) 2nd principle.
Let’s talk about the term “cryptographers” in general.

Generally talking about “cryptographers” in this context is pretty misleading, if not wrong all together. The reason is simple: it lacks specific definition. Over 100 years ago, you would be talking about academics and the military. Today, you could be talking about an amateur cryptographer without academic or military background.

We shouldn’t forget that nowadays, everyone can fire up a random search engine and learn about cryptography. 132 years ago, it was not common for “average Joe” to even be able to read.

Also – today, an interested amateur could use his computer at home to find (eg) bias in a cipher like RC4. But you can’t simply compare that to 100 years ago.

Expecting early-1900 “average Joe” to look at (and understand) cryptography is something which can not be expected or even generalized. That evolved just like the knowledge and study of Kerckhoffs principles: during a 132-year timespan, where ideas like “education for everyone” were given birth to.

TL;DR

Wrapping it up: there is no one-time-event that would mark a point where Kerckhoffs principles suddenly got accepted by most cryptographers. At least, history does not show any related ”Eureka” moment.

The knowledge and acceptance of Kerckhoffs’ principles goes hand-in-hand with the (not only academic) study of cryptography; which grew over time thanks to evolving technologies (reaching one of its many highs in the 1970’) and the general progress of modern civilisation during the past 132 years.

I’ld say that – in the broadest sense of possible interpretation – your

  So I'm starting to think the principle really has been well-understood ever since it was published, just not followed in practice by some institutions that should have known better had they asked any cryptanalyst.

is a close-to-correct[*] conclusion.

[*] The reason I wrote “close-to-correct“ is that I personally would’ve avoided using terms like “institutions”. There were ample times where there was no institution, but rather some country’s military, involved. Also, 132 years is a rather long timespan, during which (eg) the job-description “cryptanalyst” didn’t always exist.


Encrypting the same message using different schemes

Yes, $E$ will be always be secure.  This follows from a standard type of proof called a hybrid argument.  Giving the full details would be tedious, so here is a sketch in case you are familiar with hybrid arguments:

We define games $H_0,H_1,H_2$.
We let $H_0$ be the IND-CPA game, but with the game's secret bit hardcoded to $0$.  So the game always outputs $E_{1,k_1}(m_0)\|E_{2,k_2}(m_0)$ when the adversary submits $(m_0,m_1)$ as its challenge.

Next define $H_1$ to always return $E_{1,k_1}(m_1)\|E_{2,k_2}(m_0)$ always, and finally $H_2$ to always return $E_{1,k_1}(m_1)\|E_{2,k_2}(m_1)$.

A successful IND-CPA adversary $\mathcal{A}$ against $E$ is one that distinguishes $H_0$ and $H_2$.  The games $H_0,H_1,H_2$ are chosen so that we can use $\mathcal{A}$ to build adversaries $\mathcal{A}_0, \mathcal{A}_1$ to distinguish between $H_0$ and $H_1$ or between $H_1$ and $H_2$. But this will mean that at least one of the adversaries breaks the IND-CPA security of $E_1$ or $E_2$ respectively.


This is a monoalphabetic substitution cipher (with a mixed alphabet; in the first section of the article there is a paragraph about its security)

While the keyspace of this cipher is huge (relatively speaking for a classical cipher) with $26!\approx 2^{88.4}$ possible keys, it is still quite easy to break with frequency analysis.

Caesar is much worse of course, because you can simply try out all $26$ possible keys, and that is not possible for a simple substitution cipher (with arbitrary permutation).

  Does this then only leave me vulnerable to frequency analysis.

Well, that statement is true. But "more than almost nothing" doesn't mean much.


Disadvantage of the using a counter within plain text for encrypting with AES256 and authentication?

So is there any disadvantages of using this method except reduced data transfer rate?

Actually, that's a fairly major one; however another one is the possibility of someone injecting random changes undetected.

Suppose an attacker took a ciphertext block, and replaced it with random data.  Then, when you decrypt, what you come up with is effectively random data.  If the sequence number looks correct (probability $2^{-32}$ or $2^{-16}$, depending on the tag size), then it'll be accepted.  This is a higher probability than many applications will accept.  The attacker has no control over what the decryption is, for some attacks, this might be sufficient.

  Is this authentication method better than available cryptographic hash functions?

You might turn that question around; how is this method even as good as standard methods (for example, GCM)?  It uses more bandwidth, and it has weaker modification detection probability.


What do the signature security abbreviations like EUF-CMA mean?

(Notation. Sets are represented using the calligraphic font and algorithms using the straight font. Throughout, $\Sigma:=(\mathsf{K},\mathsf{S},\mathsf{V})$ denotes a signature scheme on a key-space $\mathcal{K}$, message-space $\mathcal{M}$ and signature-space $\mathcal{S}$.
Since only a single key-pair is involved in the discussion, to avoid cluttering, let's drop the security parameter, public key and secret key when invoking $\mathsf{S}$; similarly, let's drop the security parameter and public key while invoking $\mathsf{V}$. That is, we regard:
  $\mathsf{S}:\mathcal{M}\rightarrow\mathcal{S}$ and
  $\mathsf{V}:\mathcal{S}\times\mathcal{M}\rightarrow\{0,1\}$.)

As in the case of encryption schemes, security is modelled for a signature scheme $\Sigma$ using a game between a challenger and an adversary $\mathsf{A}$ (a polynomial-time probabilistic machine). The game models a possible scenario where $\mathsf{A}$ tries to break $\Sigma$ using an attack when the challenger is using the scheme $\Sigma$. $\Sigma$ is said to be secure in the  $\mathtt{break}$-$\mathtt{attack}$-model (i.e., $\mathtt{break}$-$\mathtt{attack}$-secure) if it is "difficult for any $\mathsf{A}$'' to $\mathtt{break}$ $\Sigma$ under $\mathtt{attack}$ (the precise definition is given in the end). Hence, for the case of signature schemes $\mathtt{break}\in${UF,SF,EF} and $\mathtt{attack}\in${KOA,CMA,KMA}---it is possible to consider any combination of these.

For ease of exposition, let's start with the description of the "weakest" model, called universal forgery  (UF) under key-only attack (KOA).

  1: UF-KOA$^{\mathsf{A}}_\Sigma(1^n)$

Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$
a. Challenge $\mathsf{A}$ on an arbitrary message $m^*\in\mathcal{M}$

b. Receive as response (to the challenge) a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

That is, in the UF-KOA model, the adversary has forged on a message chosen by the challenger (i.e., a universal forgery) given just the public key (i.e., the key-only attack). In this model, the adversary has the hardest-possible task: it is given only the bare minimum required to forge---i.e., the public key---and has no choice on which message to forge on.

In practice, an adversary could have means to obtain more information than this---e.g., it might procure, through some channel, a signature issued by the signer. This is not captured by the UF-KOA model and hence the reason to deem it weak. There are two ways to strengthen it: one, we could make the task of the adversary easier (e.g., let it forge on a message of its own choice); and/or two, we could provide it more information (e.g., give it signatures on messages of its choice). Let's now take a look at a model, called UF under known-message attack (KMA), that does the latter.

  2: UF-KMA$^{\mathsf{A}}_\Sigma(1^n)$

a. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

b. Sample $q=q(n)$ arbitrary messages $m_1,...,m_q\in\mathcal{M}$, and generate signatures $\sigma_i\leftarrow\mathsf{S}(m_i)$, $1\le i \le q$
a. Send the set $\{(m_1,\sigma_1),...,(m_q,\sigma_q)\}$ to $\mathsf{A}(1^n)$, and challenge it on an arbitrary message $m^*\not\in \{m_1,...,m_q\}$

b. Receive as response from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

Although $\mathsf{A}$ has to still produce a universal forgery, it now gets---unlike in the UF-KOA model---a bunch of signatures on messages it knows (the known-message attack). The model can be further strengthened by allowing $\mathsf{A}$ to query and obtain signatures on messages of its choice. This yields the model, given below, called UF under chosen-message attack (CMA).

  3: UF-CMA$^{\mathsf{A}}_\Sigma(1^n)$

a. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

b. Initialise a set $\mathcal{M}'=\emptyset$.
If $\mathsf{A}$ queries for signature on a message $m\in\mathcal{M}$, responds with $\mathsf{S}(m)$, and add $m$ to $\mathcal{M}'$
a. Challenge $\mathsf{A}$ on an arbitrary message $m^*\not\in\mathcal{M}'$

b. Receive as response from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

Next, let's look at strengthening the model from the second aspect, i.e., by weakening the notion of what it means for an adversary to break the signature scheme. We go from universal forgery, which was discussed in the first experiment, to selective forgery (SF) and finally to existential forgery (EF) in the setting of KOA.

  4: SF-KOA$^{\mathsf{A}}_\Sigma(1^n)$

Receive from $\mathcal{A}$ the commitment $m^*\in\mathcal{M}$: $\mathsf{A}$ has to forge on $m^*$ in the end
Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$
Receive as response from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

Note that although $\mathcal{A}$ has to a priori commit to the message it forges on, it still has more freedom than in the UF-KOA game---for EF-KOA, this restriction is also lifted.

  5: EF-KOA$^{\mathsf{A}}_\Sigma(1^n)$

Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$
Receive as response from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

In a similar vein, it is possible to define the models $\mathtt{break}$-$\mathtt{attack}$ for $\mathtt{break}\in${SF,EF} and $\mathtt{attack}\in${KMA,CMA}. The strongest model of the lot---i.e., EF-CMA---is defined below as it is considered to be the model on which security of signature schemes should be based on.

  6: EF-CMA$^{\mathsf{A}}_\Sigma(1^n)$

a. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

b. Initialise a set $\mathcal{M}'=\emptyset$.
If $\mathsf{A}$ queries for signature on a message $m\in\mathcal{M}$, respond with $\mathsf{S}(m)$, and add $m$ to $\mathcal{M}'$
Receive as output from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$ and $m^*\not\in\mathcal{M}'$

That is, in the EF-CMA-model, the adversary can obtain a bunch of signatures on messages it chooses adaptively, and, in the end, can forge on any fresh message. A stronger version of this definition ---called the strong EF-CMA (sEF-CMA)---is also considered desirable.

  7: sEF-CMA$^{\mathsf{A}}_\Sigma(1^n)$

a. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

b. Initialise a set $\mathcal{M}'=\emptyset$.
If $\mathsf{A}$ queries for signature on a message $m\in\mathcal{M}$, respond with $\sigma=\mathsf{S}(m)$, and add $(m,\sigma)$ to $\mathcal{M}'$
Receive as output from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$ and $(m^*,\sigma^*)\not\in\mathcal{M}'$

That is, the adversary can forge on a message on which it queried for a signature as long as the forgery is different from the one it received as a response to the query (i.e. a strong existential forgery).

P.S.

Definition. A signature scheme is said to be $\mathtt{break}$-$\mathtt{attack}$-secure if for all probabilistic polynomial-time adversaries $\mathsf{A}$
$$\Pr[\mathsf{A}\ wins\ \mathtt{break}-\mathtt{attack}_\Sigma^{\mathsf{A}}(1^n)]=negl(n).$$
where $\mathtt{break}\in${UF,SF,EF} and $\mathtt{attack}\in${KOA,CMA,KMA}.
Although, only signature schemes are discussed, the definitions can be easily adapted for message-authentication codes (MACs). In particular:

As the key generation algorithm generates only the symmetric key $k$, in Step 1 of the security models, there no key to be handed over to $\mathsf{A}$. As a consequence, UF-KOA is difficult in an information-theoretic sense.
Instead of querying for a signature on messages, $\mathsf{A}$ queries for tags.

There are other variants of attacks and breaks --- see [GMR], for example.

References:
[GMR]: Goldwasser, Micali and Rivest. A digital signature scheme secure against adaptive chosen-message attacks. (PDF)


Secret modular exponentiation with chosen modulus

Is it possible to recover the following values
$\cdot$ e

Yes, using the oracle access 2.
He can pick values $x$ and $n'$ which have small orders (and computing such values for arbitrary orders can be done efficiently [1]).  If he selects a value $x, n'$ such that $x$ has order $q$ and learn $x^e \bmod n'$, he can recover the value $e \bmod q$ in $O(\sqrt q)$ time.
So, he learns $e \bmod q_1$, $e \bmod q_2$, …, $e \bmod q_n$ are a large number of distinct small primes $q_1, q_2, …, q_n$; he then can compute the value $e \bmod q_1q_2...q_n$; if the number of small primes is sufficient, this is the value $e$

$\cdot$ m
$\cdot$ d

No; oracle 2 is of no further use (as we have recovered all the secrets it holds), and oracle 1 is the standard RSA oracle; neither the plaintext nor the private key is recoverable.
[1] Here is an efficient way to generate a pair $x, n'$ such that $x$ has order $q$

Find a prime of the form $n' = qs + 1$, for some integer $s$, and which is the size you're looking form.

Select an arbitrary value $r$, and compute $x = r^s \bmod n'$

If $x = 1$ or $x = 0$, go back to step2

[Needed only if $q$ is not prime] for every prime factor $t$ of $q$, verify that $x^{q/t} \ne 1 \pmod {n'}$; if $x^{q/t} = 1 \pmod{n'}$ for any prime factor $t$, then go back to step 2.

TA-DA!  You're done; the order of $x$ modulo $n'$ is $q$; that is, $x^q = 1 \bmod{n'}$ and $x^i \ne 1 \bmod{n'}$ for all $i \in [1,...,q-1]$


First, there is a non-security argument in favor of option 2.: if you can cache the AES key across key exchanges, you can save time in key setup. Whether that's relevant I'll leave for you to decide.

CTR fails when the same key-input pair is used twice. Let's first assume the nonces $N_a$ and $N_b$ are always unique, and that key derivation and mixing is strong.

Birthday bound for a key collision is $2^{64}$ for AES-128, $2^{128}$ for AES-256 etc.
If generating a 96-bit nonce, to use with a 32-bit counter, the birthday bound is $2^{48}$. With a 128-bit nonce and messages shorter than $2^{32}$ you can get a higher value, but unless you only have one block messages it's less than $2^{64}$.
With a 96-bit AES nonce the birthday bound is $2^{112}$ for AES-128 or $2^{176}$ for AES-256. Again, you can get a bit better bounds with a larger nonce and shorter messages, approaching $2^{128}$ and $2^{192}$.

Clearly the last is "best", but even with just a random 96-bit nonce you could have billions of key exchanges with a very small chance of even one collision. That one is a bit borderline, but any of the other options I would consider good enough.

Note the assumption made, that nonces are unique. If the nonces themselves collide, any data derived from them will also collide. For random nonces you'd want them to be at least as long as the total data derived from them. In addition, the exchange of nonces should be designed such that an attacker cannot affect it and cause a collision.

As an aside, option 3. doesn't necessarily require two sets of nonces. You can derive both a 128-bit key and a nonce with a single HMAC-SHA-256, or you can derive more material with two differently salted HMACs. Doing so will make the nonces depend on $S$, but that doesn't seem like a problem.


Advantages of making streamcipher stream depend on plaintext?

Most advantages have to do with the fact that it includes authentication. For example:

An authenticated encryption primitive is easier to use correctly.
Only a single primitive that has to be secure.
One pass over the data to both encrypt and authenticate may be faster. (Bernstein's rebuttal is that a separate MAC allows faster detection of forgeries, mitigating denial of service attacks.)

There is one potential benefit I can think of that isn't related to authentication, but it should never come into play if you are using the cipher securely:

A plaintext dependent keystream may recover from IV collisions.

This is similar to how a block cipher in CFB mode can be secure after the first block, even with duplicate IVs, if the plaintext differs.


Security level difference: supersingular vs non-singular elliptic curve

The reason why to achieve the same security level a supersingular elliptic curve requires to have a greater field size is due to the MOV attack.

In the MOV attack, for a curve $E(\mathbb{F}_p)$ you use a Weil Pairing to move the discrete logarithm from $E(\mathbb{F}_p)$ to $\mathbb{F}_{p^k}$ where $k$ is called the embedding degree of the curve.
The discrete logarithm in multiplicative groups is easier to compute due to Index Calculus methods (e.g. the NFS for logarithms).

In the MOV paper the authors showed the value of $k$ for supersingular curve must be $k\le6$ so you should choose your original field accordingly in order to land in a cryptographically strong $\mathbb{F}_{p^k}$ after the application of the Weil's pairing.

To address the question specific parameters, supersingular curves over fields with characteristic not equal to $2$ or $3$ must have embedding degree $k\leq3$.

Assuming the more conservative option is selected (i.e. $k=3$) then with your parameters $\log(q)=160$, $\log(p)=512$ an attacker applying the MOV attack will need to solve a DL in $\mathbb{F_{p^3}}$, whose order have size $512*3=1536$ bit.

Thus in this settings the curve's generator assumed solving a DL over a $1536$ bit group as complex as solving an ECDLP over $160$ bit group (unless the curve had $k=2$ in which case DL would have been over a $1024$ bit group).

The values of $k$ for general curves are, in general, much larger so that the MOV attack is less efficient than the ECDLP computation (however it is a value that should be checked when generating new curves). SafeCurves have a list of embedding degree of evaluated curves.

Edited to address the edit in the question


Can I shorten the large ECDSA public key output file from OpenSSL?

Asn1parse to the rescue.

Most of the overhead is from the base64 encoding and the PEM header and footer.

The raw size of the compressed form ASN1 encoding is just 44 bytes for my dummy key.

And 22 of those bytes are for the 161 bits of the actual public key.

$ openssl asn1parse -in compressed_public.pem -i -dump
    0:d=0  hl=2 l=  42 cons: SEQUENCE
    2:d=1  hl=2 l=  16 cons:  SEQUENCE
    4:d=2  hl=2 l=   7 prim:   OBJECT            :id-ecPublicKey
   13:d=2  hl=2 l=   5 prim:   OBJECT            :secp160k1
   20:d=1  hl=2 l=  22 prim:  BIT STRING
      0000 - 00 03 ca f2 7b b8 4c 3c-99 b2 7a 6f fb f3 cf 8f   ....{.L<..zo....
      0010 - 95 b8 77 61 76 dc                                 ..wav.

And if you turn the PEM encoding into raw DER encoding like so...

$ openssl ec -pubin -in compressed_public.pem -outform der -out compressed_public.der
read EC key
writing EC key

...then 44 bytes is the size of your file.

$ stat compressed_public.pem | grep Size
  Size: 113             Blocks: 1          IO Block: 65536  regular file

$ stat compressed_public.der | grep Size
  Size: 44              Blocks: 1          IO Block: 65536  regular file

And just for another look at this: using "dumpas1n", you can see exactly where those 22 non-pubkey bytes went:
(Note: dumpasn1 skips the "00" byte at the beginning of the 22 byte "BIT STRING" object and does not display it. And openssl asn1parse does not.)

$ dumpasn1  | head -n2
DumpASN1 - ASN.1 object dump/syntax check program.
Copyright Peter Gutmann 1997, 1998.  Last updated 27 July 1998.

$ dumpasn1 compressed_public.der
   0 30   42: SEQUENCE {
   2 30   16:   SEQUENCE {
   4 06    7:     OBJECT IDENTIFIER ecPublicKey (1 2 840 10045 2 1)
  13 06    5:     OBJECT IDENTIFIER '1 3 132 0 9'
            :     }
  20 03   22:   BIT STRING 0 unused bits
            :     03 CA F2 7B B8 4C 3C 99 B2 7A 6F FB F3 CF 8F 95
            :     B8 77 61 76 DC
            :   }

0 warnings, 0 errors.

So to answer your question:

  Can I somehow reduce this size, getting rid of metadata?

Yes. You could cut the size down to just the 22 bytes (or 21 bytes if you exclude any leading 00 bytes).

(If you want yet another tool to look at ASN1: Here's that key in asn1js online.)


Battleship game state save so players can't look up each others' states but server can

You don't even need the server to decrypt.
You need players to commit to their initial board by providing a hash of the board(probably with extra random data to increase entropy).
They can then play as usual. And save the game in encrypted form using independent keys.
At the game end commitment are to be revealed to verify no cheating.
The server need not do anything beyond store information and optionally forward messages.
Alternatively if you have a trusted server, skip encryption of state entirely, only have both parties authenticate to the server, and communicate with it over a secure channel (e.g HTTPS) and the server will enforce permissions and let each player see only their own state.


Strategy for random CTR initial counter values

Let $2^m$ be the average message length in blocks.

When using an independent random nonce for the whole 128-bit IV of each block, you would expect a collision after $2^{64}$ blocks, i.e. $2^{64-m}$ messages. (But you double the data size.)

When using a 96-bit nonce and a 32-bit counter, you would expect a nonce collision after $2^{48}$ messages. This is better than the above if $m > 16$ and of course more efficient because fewer nonces are generated.

When using a 128-bit initial nonce for the message that gets incremented for subsequent blocks, the math gets a bit trickier. The probability that two $2^m$-block messages get overlapping counter ranges is about $2^{-(128-m-1)}$ because they overlap when the second message has an initial nonce within $2^m$ of the first in either direction. That would mean at least $2^{64 - (m+1)/2}$ messages, which is better than either of the above if $1 < m < 32$.
The exact message length distribution affects how many blocks vs. messages can be sent, but normally there's a practical maximum on message size which is not orders of magnitude larger than the average, so changing $m$ above to reflect that would give a worst case estimate.

Letting the next message continue from the previous nonce until a reset would be the same as above, but with longer "messages" equal to the concatenation of all those sent between resets. With $2^k$ messages between resets that's at least $2^{64-(m+k+1)/2}$ expected sessions before a collision, i.e. $2^{64-(m-k+1)/2}$ messages, which is better if $k>0$.
However, if you assume an attacker who can control when resets happen, it becomes worse. After each message the attacker can either cause a reset (if no collisions are in the near future) or let the counter continue its journey towards a collision. Reusing the $k$ from above for a normal reset frequency the attacker can expect, two resets would have about a $2^{-(128-m-k)}$ chance of collision so the expected number of resets before collision is on the order of $2^{64-(m+k)/2}$, which is worse than the previous option.

Use the 96-bit nonce and 32-bit counter construction, but keep track of where the previous message ended. As long as there's space for the message within the 32-bit block defined by the nonce, select the IV so that it continues from where the previous message ended. If the block runs out or the device has been reset since the previous message, choose a new one randomly.
In the best case you stuff $2^{32-m}$ messages per nonce and get a collision only after $2^{48+32-m}=2^{80-m}$ blocks, which is better than any of the above. Even in the worst case where an attacker resets the device after each message you are guaranteed the $2^{48}$ expected messages before collision.

In practice I would choose the 32-bit counter, with or without the optimization for continuing from a previous message – i.e. either 2. or 5. above. There's no attack that can make it worse than $2^{48}$ messages and the math is easy.


A character is usually encoded as an ASCII. This means that it uses up one byte. That's a number from $0 - 255$. It can be represented as a hexadecimal $\text{0x00} - \text{0xFF}$. All your operations must be done character by character. From now on by "message", "key" and "cipher" i mean a single $0-255$ number.
$$
message1 \oplus key = cipher1 \\
message2 \oplus key = cipher2
$$
when we xor two ciphered letters
$$
cipher1 \oplus cipher2 = \\ message1 \oplus key \oplus message2 \oplus key = \\
message1 \oplus message2
$$
So when we xor one character of the cipher with corresponding character of a second cipher we remove the key from the equation, and receive a character of first message xored with character of second message. Now we do some deduction. We look for numbers looking like $\text{0x42}$ I did some calculations previously and I know that we can get this number within a-z(space)A-Z only by xoring "b" (lowercase b) and " " (space). Rest is pretty much a lot of guessing.

To get that byte of the key all you need is to xor byte of message with byte of cipher.
$$
key = message \oplus cipher
$$
Example:
We have two ciphertexts from which we take the third character:
$$48A6\color{red}{48}3C\\7692\color{red}{0A}A2$$
We xor them together:
$$\text{0x48} \oplus \text{0x0A} = \text{0x42}$$
I made myself a table of all possible letters xored with space, and I see that $\text{0x42}$ is in that table. This means that it's possible that one of the letters is "b" ($\text{0x62}$) and second is " " ($\text{0x20}$)
Let's assume that " " is encrypted in first ciphertext and get the key:
$$\text{0x48} \oplus \text{0x20} = \text{0x68}$$

If we assume that " " is encrypted in second ciphertext we get another possibility of the key:
$$\text{0x0A} \oplus \text{0x20} = \text{0x2A}$$

So the key can be:
$$\_\_\_\_\color{red}{68}\_\_$$
or
$$\_\_\_\_\color{red}{2A}\_\_$$

We just decreased the number of possibilities for this byte of the key from 256 to 2.


Deterministic Counter Mode with a PRF. What does evaluate at a point mean?

Let $E(k,b)$ be the AES encryption of message $b$ with the key $k$ where size of $b$ is 128-bit, the key size can be 128,192,and 256 bits.

What exactly does he mean by "Evaluating at point 0, point 1" etc

Evaluating at point 0 :  $c_0 = E(k,0)$
Evaluating at point 1 :  $c_1 =E(k,1)$
Evaluating at point 2 :  $c_2 = E(k,2)$
and soo on
Evaluating at point $\ell$ : $c_\ell=  E(k,\ell)$

$$c_i = E(k,i)$$ and the encryption is performed as
$$C_i = c_i \oplus m[i]$$

i.e. something like

There is no padding there like the PKCS#5 etc; the input $i$ is considered as a 128-bit binary encoded representation of integer $i$, or one can think of it as a 128-bit counter. We can see it more clearly if we consider the below as hex
00000000000000000000000000000001
00000000000000000000000000000002
00000000000000000000000000000003
00000000000000000000000000000004
..
000000000000000000000000000000FF
..

What is defined here is the CTR mode of operation that is first defined for PRFs and introduced by Whitfield Diffie and Martin Hellman in 1979

Privacy and Authentication: An Introduction to Cryptography as an invited paper on Proceedings of the IEEE, 67 (1979), pp. 397–427.

CTR turns a PRF into a stream cipher, as Snuffle turned into Salsa20 and AES into AES-CTR. Note that although not proved the AES is a candidate for a $PRP \subset PRF$. The CTR mode doesn't require the decryption of AES ( or any block cipher) and this is useful to reduce the area of the software/hardware implementations.


AES Affine Transformation Polynom Representation

One way to derive the values $\lambda_0, \lambda_1, ..., \lambda_7$ would be to formulate the eight simultaneous equations in GF(256):

$$\lambda_7 01^{128} + \lambda_6 01^{64} + \lambda_5 01^{32} + \lambda_4 01^{16} + \lambda_3 01^{8} + \lambda_2 01^{4} + \lambda_1 01^{2}  + \lambda_0 01^{1}  = Aff(01)$$
$$\lambda_7 02^{128} + \lambda_6 02^{64} + \lambda_5 02^{32} + \lambda_4 02^{16} + \lambda_3 02^{8} + \lambda_2 02^{4} + \lambda_1 02^{2}  + \lambda_0 02^{1}  = Aff(02)$$
$$\lambda_7 04^{128} + \lambda_6 04^{64} + \lambda_5 04^{32} + \lambda_4 04^{16} + \lambda_3 04^{8} + \lambda_2 04^{4} + \lambda_1 04^{2}  + \lambda_0 04^{1}  = Aff(04)$$
$$...$$
$$\lambda_7 80^{128} + \lambda_6 80^{64} + \lambda_5 80^{32} + \lambda_4 80^{16} + \lambda_3 80^{8} + \lambda_2 80^{4} + \lambda_1 80^{2}  + \lambda_0 80^{1}  = Aff(80)$$

(where $Aff$ is the affine transform, not counting the addition of the constant), and 80 is the GF(256) element represented by the bit pattern '10000000')

and solve this set of 8 linear equations in $\lambda_0, \lambda_1, ..., \lambda_7$

Both sides of these equations are linear; that is $(x^{2^k} + y^{2^k}) = (x+y)^{2^k}$ and $Aff(x) + Aff(y) = Aff(x+y)$, and so if find such a set $\lambda_0, \lambda_1, ..., \lambda_7$, that set will hold for a sum of any subset of (01, 02, 04, ..., 80); since that's the entire field $GF(256)$, we have:

$$\lambda_7 x^{128} + \lambda_6 x^{64} + \lambda_5 x^{32} + \lambda_4 x^{16} + \lambda_3 x^{8} + \lambda_2 x^{4} + \lambda_1 x^{2}  + \lambda_0 x^{1}  = Aff(x)$$

for all $x$.


There already exist standard primes that might be used for Finite Field Discrete Logarithm based schemes. One set is found in RFC 3526. Another set is currently in the process of being standardized as part of TLS and can be found in the current Negotiated FF DHE draft (this link will expire no later than June 15 2015).

The smallest prime in the former set is 1536 bits, which means that it is greater than $2^{1535}$. It is recommended to be used with a 180 bit exponent, which corresponds to an integer greater than $2^{179}$.

The smallest prime in the latter set (TLS) is currently fixed at 2048 bits, although an even greater number was originally proposed.

By comparison, 7 is only 3 bits and 3 is only 2 bits, so, yes, your implementation would be kind of inadequate, should you try to use these primes.


In which case number field sieve/index calculus is faster for solving discrete logarithm?

Using its notation, the question is about the difficulty of the Discrete Logarithm Problem in a Schnorr Group modulo $P$, of prime order $q$. I'll assume $b^q\bmod P=1$ and $b\bmod P\ne1$.
That DLP problem is finding $c$ chosen at random in $[0,q)$ given $P$, $q$, $b$, and $a$ obtained as $b^c\bmod P$. Depending on parameters, the best known algorithms fall into two complexity classes:

somewhere between $\mathcal O(\sqrt{q}\,\ln P\,\ln\ln P)$ [in theory] and $\mathcal O(\sqrt{q}\,\ln^2 P)$ for Baby-Step/Giant-Step and it's practical improvement: Pollard's Rho with distinguished points (which can be efficiently distributed and requires little memory; see Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999). The cost is often stated as $\mathcal O(\sqrt{q})$ multiplications of integers of size $P$, and this has been recently shown to cost $\mathcal O(\ln P\,\ln\ln P)$, see this.

something like $\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln P)^{\frac{1}{3}}(\ln \ln P)^{\frac{2}{3}}\right)$, for the Number Field Sieve applied to the Discrete Logarithm (see this).

in which cases is NFS/Index Calculus used?

For a given size of $q$, the first class of algorithms (Pollard's Rho..) is best for large $P$. The second (NFS) is faster for relatively small $P$, including $q$ a Sophie Germain prime (equivalently, $P$ a safe prime).
For 256‑bit $q$, the first class of algorithm is better for 8192-bit $P$, the second for 512‑bit $P$. I prefer not digging where exactly the crossover is, or what's the exact difference between NFS and IC.


How does the verification process associated with this signature scheme work?

Sorry, can't comment yet. So I'm going be more verbose since it's an answer ;)

I get other values for $z$ and $s$:
$$h^{-1} = 2441\mod q-1 $$ and
$$z = x \cdot h^{-1} = 3612\mod q-1\\
\Rightarrow s = a^z = 1039\mod q$$

The hash value $h$ can be reduced since we
are working modulo $q$. With $q$ prime we have $\phi(q) = q-1$ and
we can reduce the exponent modulo $q-1$.

This gives
$$y' = s^h = s^{h\mod q-1} \mod q\\$$
So with $h \equiv 2297 \mod q-1$ we verify:
$$y' = 1039^{2297}\mod 6043 = 485 = y$$
as desired.


For any $x,y$ represented by $\{0, 1\}$, $x \lor y = 1 - (1-x)(1-y)$. It follows, any one-multiplication homomorphic scheme would do. It also follows, just additively homomorphic scheme would be not enough.


random oracle model vs standard model vs selective model

In the random oracle model, you assume the existence of random behaving function, which is at the control of the protocol designer-challenger- during the game played between the adversary and the challenger in case of game based definitions. Usually the challenger manipulates the random looking output at its will in order to 'inject' the challenge of a presumably difficult problem like DDH, CDH, etc. In the real world, the random oracle advocates conjecture that this can be instantiated with a collision resistant hash function and argue that if such function raises security problems then we just replace it but the model itself does not break. This is still questionable as researchers have manage to cancel security guarantees by exploiting the non-random-looking instantiation of such hash functions.
In the standard model, there is no assumption for the existence of such random looking function and the security of the scheme lies on the hardness of mathematical assumptions, usually at the cost of a less efficient protocol but without making any assumption about random functions.
Selective model cannot be compared with random oracle and standard model. It is like comparing apples with lemons. Selective model dictates the way an adversary is getting information from the challenger (paper). In the selective model the adversary somehow declares in advance the challenge is gonna get later in the protocol. That renders the model a bit weak. In contrast in the adaptive model this limitation does not exist.


Yes, if you are using 3rd party key exchange, the 3rd party can read the messages. If that is not the security feature you want, use something else. There are many legitimate scenarios where users are fine with trusting the third party, however. For example, a system setup by my employer to allow encrypted chat between myself and our clients. My employer has legitimate reasons to want to be able to access those messages if necessary and so would want to set it up with (possibly) third party key exchange. I, as an employee, might be fine with that as I would be conducting official company business using the system.

Older protocols might have done this before public-key crypto was invented in order to keep key management reasonable.


Using nested signatures to trust public key of inner signatures

I think this depends heavily on the expectations and trust that A has with respect to C.  $A$ should be safe to now view $P_B$ as authentic provided that $A$ trusts that:

$C$ will only sign $B$'s message if it could successfully verify $S_B(M)$
$C$ would only use $P_B$ if it had previously obtained and verified the authenticity of $P_B$
$C$'s requirements for verifying the authenticity of $P_B$ are at least as strict as $A$'s

Note that this is essentially the same as with certificate authorities, where $P_x$ are X.509 certificates (e.g. $P_C$ is the root certificate for a CA, $C$).  $B$ can't expect to provide $P_B$ to everyone it expects to communicate with so instead it establishes trust with $C$ which then signs $P_B$.  When $A$ receives data from $B$, it would first receive $P_B || S_C(P_B)$ then $M || S_B(M)$.  $A$ then decides to trust $P_B$ on the grounds that $C$ would not have signed $P_B$ without first establishing it's authenticity. $A$ then, in turn, trusts that $M$, in fact, originated from $B$.

However, it's important to note the $A$ having authenticated $P_C$ is not sufficient.  Messages signed with $S_C$ may, in fact, be coming from $C$ but that does not mean that $C$ is fully trustworthy.  For $A$ to trust $C$'s trust of $P_B$, $A$ must also trust that $C$ is sufficiently cautious about establishing the authenticity of $P_B$.  Just as it would be extremely concerning if a trusted certificate authority were to start signing any certificate sent their way, $A$'s confidence in the authenticity of $M$ and $P_B$ must not be greater than $A$'s confidence in $C$'s process of establishing trust.

Similarly, if $C$ viewed its job simply as marking that it received and relayed the message, blindly signing the entire payload it received, $A$ would be mistakenly assuming an assurance not actually provided by $C$.

Long story short: $A$ can only trust $P_B$ if it trusts that $C$ is, and is sufficiently capable of, guaranteeing the authenticity of $P_B$.


How does this POLYVAL modular reduction algorithm work?

From the paper if you look at section 2.3 you will find an explanation of the reduction. The reduction from a code execution prospective works by reducing the number of operations of GHASH.
From a theoretical stand point the paper authors took an incorrect derivation direction of the first induction proof. However their mistake resulted in discovering a differential set linkage between POLYVAL and GHASH.
Where A ^ B --->  D0  and Z* is the number of checks to determine the value of D0. After completing running GHASH the function returns D*. From this the operator can say B ---> D0 and Z < Z*.


Multi Key Encryption but read only part of data

every key is only allowed to read/decrypt only a certain part of the document

How about encrypting those parts with separate keys?


One obvious way (which is a variant of the normal time-lock encryption technique) is to do RSA encryption, with a truly huge $e$.

That is, to encrypt, you compute $M^{3^\lambda} \bmod N$; by making $\lambda$ sufficiently large, you can make this take a long time.

To decrypt, you would have precomputed the values $(3^\lambda)^{-1} \bmod p-1$ and $(3^\lambda)^{-1} \bmod q-1$, which can be done in $O(\log \lambda)$ time; you proceed with RSA decryption in the standard way.


Attribute-based encryption for cloud storage

It is related to Cloud storage in the sense that you don't have to trust the server you put your data on.
Usually, the access control is done via authentication. This requires the server to be trusted.
However in the case of Cloud storage, you don't know anything about the server hosting the data, so being able to do access control with the encryption scheme is great.


Where is the proof of security of Diffie's cipher?

This looks totally weak. If you know 128 bits of known plaintext, you can infer the corresponding 128 bits of keystream. The keystream being the multiplication of the random matrix by the key (in the vector space $\mathbb{F}_2^{128}$), the key is then revealed through a basic matrix inversion.


Correct way to read a given permutation cipher?

The permutations in your question are given in Cauchy's two-line notation, where the upper line gives the input index to the permutation function, and the lower line gives the resulting permuted index.

For example, the definition $$\sigma = {1\ 2\ 3 \choose 3\ 1\ 2}$$ means the same as $$\sigma(1) = 3,\quad \sigma(2) = 1,\quad \sigma(3) = 2.$$  Thus, if we apply this permutation $\sigma$ to a tuple $x = (x_1, x_2, x_3)$, we obtain the permuted tuple $$x_\sigma  = \sigma \cdot x = (x_{\sigma(1)}, x_{\sigma(2)}, x_{\sigma(3)}) = (x_3, x_1, x_2).$$

In particular, if $x = (x_1, x_2, x_3) = (\text{V}, \text{E}, \text{N})$, then $x_\sigma = (x_3, x_1, x_2) = (\text{N}, \text{V}, \text{E})$.

This is easy visualize if you simply replace the indices $1$, $2$ and $3$ in the definition of the permutation with the elements $x_1 = \text{V}$, $x_2 = \text{E}$ and $x_3 = \text{N}$ to be permuted, giving $${x_1\ x_2\ x_3 \choose x_3\ x_1\ x_2} = {\text{V E N} \choose \text{N V E} }.$$

The second example in your question appears to be incorrect: given the permutation $$\sigma' = {1\ 2\ 3 \choose 2\ 3\ 1}$$ and the input $x' = (x'_1, x'_2, x'_3) = (\text{T}, \text{E}, \text{N})$, the output should be $$x'_{\sigma'}  = \sigma' \cdot x' = (x'_{\sigma'(1)}, x'_{\sigma'(2)}, x'_{\sigma'(3)}) = (x'_2, x'_3, x'_1) = (\text{E}, \text{N}, \text{T}),$$ not $(x'_3, x'_1, x'_2) = (\text{N}, \text{T}, \text{E})$.  It would, however, be correct if we replaced the permutation $\sigma'$ with its inverse $$\sigma'^{-1} = {2\ 3\ 1 \choose 1\ 2\ 3} = {1\ 2\ 3 \choose 3\ 1\ 2}$$ (which, as it happens, equals the first permutation $\sigma$) obtained by swapping the rows and (optionally) re-sorting the columns in the two-line definition of $\sigma'$.


Is it possible that a signing algorithm produces no output?

I just can't imagine an algorithm that doesn't give an output wherein the algorithm above, it seems that it will always produce a certain output.

Actually, step 1 is randomized; that is, it will select a value of $r$ randomly (from some probability distribution).  If step 4 decides to rerun the procedure, then step 1 will likely generate some different value, and so the output would be different.

  It also seems to violate the definition of an algorithm by Knuth.

Well, by Knuth's definition, it's a "computational method" rather than "an algorithm".  I don't think, in this case, the distinction is important, as the algorithm will terminate with probability 1 (and terminate quickly with high probability).  I don't believe that Knuth had randomized procedures (like this one) in mind when he wrote his definitions...


AES: Given two deterministic plaintexts, compute two keys let the ciphertext is the same, is it possible?

What is the mathematical property stating that it is hard to find a collision in the AES algorithm?

The answer of Lindell is important.

For an adversary with infinite computation power it is always possible to find $p_1$ and $p_2$ s.t. $E_{k_1}(p_1) = E_{k_2}(p_2)$. Choose any values $k_1, k_2$ with $k_1 \neq k_2$ and calculate $p_3 = E^{-1}_{k_2}(E_{k_1}(p_1))$ and stop if $p_3 = p_2$, otherwise repeat with different $k_2$.

However if the question is how easy it is to find such $k_1, k_2$ it is a different story.


Information-theoretic bound on leakage by timing measurement

As you say, if the measurements are accurate then the device can leak $log_2(n)$ bits of information on each invocation.  If it lacks internal storage then it can't track which parts of the key it has already leaked.  What it can do is leak a random set of bits, but the recipient has to know which bits they are.  I see two approaches.

If the timing channel is the only communication, then the $m = log_2(n)$ bits has to combine both key data ($d$ bits) and position ($p$ bits).  If position indicates which group of $d$ bits we are leaking, then $p >= log_2(k/d)$.  So for a 256 bit key this scheme requires that you be able to leak at least 9 bits at a time: 8 bits to indicate the key position and 1 for that key bit.  The position bits would be randomly generated.

Another approach would be to communicate the position differently: instead of using an RNG to select the position and include that in the leaked data, you could use data from the ciphertext if your threat model includes the attacker seeing that.  You could use the first $p$ bits of the ciphertext to choose/signal which key bits we are leaking, where $p = log_2(k/m)$.

In both cases, the solution to how long it takes to leak all $k$ bits of the key is given by the Coupon Collector's Problem, which is $O(n log n)$.  In the second example, this should come out to $O(k/m log(k/m))$.  Of course you don't have to wait to collect all of the sections.  Especially with a low bandwidth channel it would make sense to start brute-forcing as soon as feasible.


In lieu of any answers; I've compared my own implementation with the few test vectors I've been able to find (one of which can be found here) and it would appear that yes, keys longer than the block-size are hashed and zero-padded. It feels counter-intuitive to shorten a key and zero-pad it, but that's what the specification stipulates.


This question and answer covers the requirements of a key schedule.

I could not find a simpler description of Camellia then this rfc

The following excerpt outlines the key schedule. Addressing only the 128 bit cipher for simplicity:

128-bit key K:
KL = K;    KR = 0;
...

  The 128-bit variables KA and KB are generated from KL and KR as
     follows.  Note that KB is used only if the length of the secret key
     is 192 or 256 bits.  D1 and D2 are 64-bit temporary variables.  F-
     function is described in Section 2.4.

   D1 = (KL ^ KR) >> 64;
   D2 = (KL ^ KR) & MASK64;
   D2 = D2 ^ F(D1, Sigma1);
   D1 = D1 ^ F(D2, Sigma2);
   D1 = D1 ^ (KL >> 64);
   D2 = D2 ^ (KL & MASK64);
   D2 = D2 ^ F(D1, Sigma3);
   D1 = D1 ^ F(D2, Sigma4);
   KA = (D1 << 64) | D2;
   ...

  The 64-bit constants Sigma1, Sigma2, ..., Sigma6 are used as "keys"
     in the F-function.  These constant values are, in hexadecimal
     notation, as follows.

Sigma1 = 0xA09E667F3BCC908B;
Sigma2 = 0xB67AE8584CAA73B2;
Sigma3 = 0xC6EF372FE94F82BE;
Sigma4 = 0x54FF53A5F1D36F1C;
Sigma5 = 0x10E527FADE682D1D;
Sigma6 = 0xB05688C2B3E6C1FD;

  64-bit subkeys are generated by rotating KL, KR, KA, and KB and
     taking the left- or right-half of them.

It appears the first part of the key schedule is a Feistel network as well: The right half is combine via XOR with F(left half, key), using a constant (SigmaN) for each of the keys. Then this process continues alternated, and some key additions are applied.

Actual round subkeys are generated via simple rotations of the result of the above. So recovery of one subkeys bits provides partial knowledge of the bits of other round subkeys.

This would appear to classify as a type "1B" key schedule, according to the classification system presented in this paper.

The strongest key schedule classification is "2B". For more details on the classification and what exactly it indicates, consult the paper linked at the top of this answer.


Schnorr signature using discrete logarithm / problem with python implementation

Beware, notice the $s$ is computed modulo $(q-1)$ (due to Fermat's little theorem).
You have to write $s = (k - (x * e)) \mod{ (q-1)}$.


How to thwart a cleartext message's size?

This is a complex question. There exists no formal treatment of this question and the parameters you choose will depend on your application. A method that is typically used is, like you said, to append some padding to your plaintext. Note that you don't need to both append and prepend; appending is sufficient. Also, the padding doesn't have to be random, it can be deterministic (for instance 0x0000 or something else that is convenient for your file format).

A method that is typically used is to split your data into certain prespecified buckets of a certain size; for instance 1KB, 10KB, 50KB, 1MB and 10MB. Then when your data is transmitted, you round up to the nearest bucket by appending padding.

A few years ago, I worked for the Twitter Product Security team where I performed length-based attacks and defences. This "bucket" technique is something the Twitter product security team does nowadays to avoid profile fingerprinting.

Here's the attack. Suppose I'm your ISP and I want to find out if a certain "suspicious" Twitter profile belongs to one of my customers (we suspect that this attack has actually happened in the real world with devastating consequences [0]). The way I do this is I monitor all of the HTTPS responses that contain the twitter.com SNI. I look at the length of these responses and I count how many times you visit a page of a particular length during a short period of time, say, a few minutes. Specifically, I look at "bursts" of responses which correspond to a particular mouse click and contain multiple files such as HTML, CSS, and JPG. For all of these files, I can calculate the length of the ciphertext. In case of newest HTTPS protocol versions, I can only get a global length for this particular "burst", but this should be enough to fingerprint.

The length I see you visit most often likely corresponds to the length of the page corresponding to your own twitter feed (i.e., what you see when you go to twitter.com). Now, because the "suspicious" Twitter profile I'm interested in has a public list of people they follow, I can reconstruct that feed, because all it contains are tweets by the people they publicly follow (assuming here that secret tweets are rare). In this reconstruction, I know which avatars of which people should appear in the feed. Those will have to be transmitted as images over HTTPS and their sum is added to what I see. I can also reasonably predict if and when some of them are being cached so that they're not retransmitted. Therefore, if the page you visit most often has a similar length to the feed of the "suspicious" Twitter profile feed, I can deduce that it's you.

In the bucket defence, avatars always have a certain size among 10 different sizes. The way this is achieved is that padding is added as needed. There's also a maximum size that you can't upload beyond.

If you have rigorous requirements about what kind of thing you want to hide, you can look at differential privacy [1]. This can help you understand exactly how much noise you need to add in order to confuse the adversary to a certain degree. It will also allow you to quantify how many queries the adversary would need to perform in order for them to get to your length within a specified margin of error. This depends on your application. If you provide more comments about what you're trying to do and what your threat model is, it would be helpful.

There are some details related to this attack that are interesting and can cause engineering challenges, but they can be overcome. The first is that stream ciphers preserve byte length between plaintext and ciphertext, but block ciphers do not preserve it exactly. This can cause problems in measurements, but they only delay the attack, because there is still enough information to be gained if you just round up to the closest 256th bit. This is something we explored in our work [2] where we augmented BREACH to work against AES and not only RC4. The second is that data is compressed and compression is a complex thing which composes multiple algorithms which can compress across different sources of data. Again, this may make things more difficult, but still allows statistics to be run. Last, there's noise in all of these pages, such as ads, recommendations and so on that the adversary cannot predict. But these do not affect the page lengths dramatically, and in any case they can be modelled as "uniformly random noise" which, on average, adds a constant length to the response. In fact, the existence of appropriate compression and the adversarial manipulation of noise can allow an adversary to vastly improve their attack. For some of the techniques we developed to this end, as well as some defences, see our collaborative work at [3, 4, 5, 6].

For a formal treatment, you can consult our incomplete and unreadable manuscript on the theory [7]. Sadly, I do not think this manuscript will ever be finished and I don't think I can take the security games and proofs to where I wanted.

[0] McGahan, Jason. "She Tweeted Against the Mexican Cartels, They Tweeted Her Murder". October 2014. Accessed May 2018.

[1] Dwork, Cynthia. "Differential privacy: A survey of results." International Conference on Theory and Applications of Models of Computation. Springer, Berlin, Heidelberg, 2008.

[2] Karakostas, Dimitris and Zindros, Dionysis. "Practical New Developments on BREACH". Black Hat Asia 2016. Presentation.

[3] Grigoriou, Dimitris. "Extending the Rupture compression attack framework against real world systems". University of Athens 2017.

[4] Karakostas, Dimitris and Kiayias, Aggelos and Sarafianou, Eva and Zindros, Dionysis. "CTX: Eliminating BREACH with Context Hiding". Black Hat Europe 2016.

[5] Karakosats, Dimitris. "Probabilistic Attacks Against Compressed Encrypted Protocols". National Technical University of Athens 2016.

[6] Sarafianou, Eva. "Creating a Tool for Attacking Compressed Encrypted Protocols". National Technical University of Athens 2017.

[7] Karakostas, Dimitris and Kiayias, Aggelos and Zindros, Dionysis. "On the (in)security of encryption over compression in TLS". Unfinished manuscript. Source.


(I write a more extensive answer with the background of all this; the result you are looking for is Theorem 3. A proof would be too long for this site, you can consult standard textbooks.)

Let $E$ be an elliptic curve over $\mathbf{F}_p$ and $P \in E(\mathbf{F}_p)$ be a point of prime order $r \ne p$. So $r$ divides the order of $E(\mathbf{F}_p)$, and suppose further that $r^2$ does not divide the order of $E(\mathbf{F}_p)$. For any extension field $K$ of $\mathbf{F}_p$, we let $E(K)[r]$ be the group of all points $Q \in E(K)$ such that $rQ = \infty$. Note that $P \in E(K)[r]$, so $\langle P\rangle$ is a subgroup of $E(K)[r]$.

Theorem 1. The group $E(\overline{\mathbf{F}_p})[r]$ is isomorphic to $\mathbf{Z}_r \oplus \mathbf{Z}_r$.

Corollary. There is an integer $k > 1$ such that $E(\mathbf{F}_{p^k})[r]$ is isomorphic to $\mathbf{Z}_r \oplus \mathbf{Z}_r$.

In the following, we let $k$ be the smallest such integer (called the embedding degree), $K = \mathbf{F}_{p^k}$, and $E[r] = E(K)[r]$. Thus all the points of $E[r]$ have coordinates in $K$.

Then the mathematician's Weil pairing $e_r$ is a map from $E[r] \oplus E[r]$ to $\mathbf{F}_{p^k}^*$ with the following properties (among others), which makes it different from the cryptographer's pairing.

Bilinearity. For all points $P,Q,R \in E[r]$ we have
$$
\begin{align*}
e_r(P+Q,R) &= e_r(P,R)\times e_r(Q,R), \text{and} \\
e_r(P,Q+R) &= e_r(P,Q)\times e_r(P,R).
\end{align*}
$$

Alternacy. For all points $P \in E[r]$, we have $e_r(P,P) = 1$.

Non-degeneracy. For all points $P \in E[r]$, if $e_r(P,Q) = 1$ for all points $Q \in E[r]$, then $P = \infty$.

The property of alternacy of the Weil pairing makes it unsuitable for cryptography, since in cryptography we require $e(P,P) \ne 1$. So the Weil pairing needs to be modified.

Theorem 3. Let $P,Q \in E[r]$. Then $e_r(P,Q) = 1$ if and only if $Q$ is a multiple of $P$.

Corollary 1. A point $Q \in E[r]$ has coordinates in $\mathbf{F}_p$ if and only if it is a multiple of $P$.

Corollary 2. The group of $r$th roots of unity in $K$ is cyclic of order $r$.

In the following, let $Q$ be a point of $E[r]$ which is not a multiple of $P$. This implies that $Q$ (which has coordinates in $\mathbf{F}_{p^k}$) does not have coordinates in $\mathbf{F}_p$. Let $G = \langle P\rangle$, and let $G_T$ be the group of $r$th roots of unity in $K$ (both groups are cyclic of order $r$).

We define the modified Weil pairing $\hat{e}_r$ as a map from $G \times G$ to $G_T$ such that $\hat{e}_r(P,P) = e_r(P,Q)$. Then $\hat{e}_r$ is a suitable cryptographic pairing: its bilinearity follows from the bilinearity of $e_r$, and its non-degeneracy (in the cryptographic sense) follows from Theorem 3 since $Q$ is not a multiple of $P$.

There are many ways to do this in practice, one is to let $p \equiv 2 \pmod 3$ and such that $(p+1)/6$ is prime. In this case the curve $Y^2 = X^3 + 1$ has $p+1$ points (it is supersingular) and we can choose a point of order $r = (p+1)/6$. It can also be shown that in this case, we have $k = 2$. Since $p^2-1$ is a multiple of $3$, there is a primitive $3$rd root of unity in $K = \mathbf{F}_{p^2}$, call it $\zeta$. Then for a point $P = (x,y)$, the point $Q$ is $(\zeta x, y)$.


Discrete Logarithm: Given a p, what does it mean to find the discrete logarithm of x to base y?

Discrete Log for arbitrary Groups: Discrete Log can be defined in arbitrary groups and some groups can have an easy solution (powers of 10) and some can have a hard solution.

Let $G$ be any group and $\odot$ be the group operation. For any $k \in \mathbb{Z}_{>0}$, let $b \in G$ then we define $[k]b =  \overbrace{b\odot\cdots\odot b}^{{k\hbox{ - }times}} $. Then for a given $a \in G$ the $k$ that satisfies $[k]b = a$ is called discrete log of $a$ to base $b$. It can also be written as $k = \log_b a$

Additive DLog : The analogous definition for $(\mathbb{Z}_p,+)$ is well-defined with given $a,b,n$ find $x>0$ such that $x a \equiv b \bmod n$. It can be solved easily  if you find the inverse of $a$ by using the Ext-GCD algorithm.
Multiplicative DLog :, the discrete Logarithm Problem (DLP) is given $a,b,n \in \mathbb{Z}^+$ find $x \in \mathbb{Z}_{>1}$ such that $a^x \equiv b \bmod n$, if such $x$ exists.

For the small modulus we can build a table for the DLP problem, or you can stop building the table whenever you find your case.

The below is a DLog (Discrete Log) table for modulus 19 with base 2.

\begin{array}{c|rrrrrrrrrrrrrrrrr}
x&  1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& \color{red}{13}& 14& 15& 16& 17& 18\\ \hline
2 ^x \bmod 19&  2& 4& 8& 16& 13& 7& 14& 9& 18& 17& 15& 11& \color{red}{3}& 6& 12& 5& 10& 1
 \end{array}

For example, given 3 as the DLog base 2 modulo 19, we will look for 3 in the second row and corresponding $x$ in the first row that is 13. I.e. $2^{13} \equiv 3 \bmod 19$

Different bases will produce different tables; for base 5:

\begin{array}{c|rrrrrrrrrrrrrrrrr}
x&  1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18\\ \hline
5 ^x \bmod 19&  5& 6& 11& 17& 9& 7& 16& 4& 1& 5& 6& 11& 17& 9& 7& 16& 4& 1
\end{array} If you know the relation with the two bases then you don't need to calculate another base.

This approach is actually is brute-forcing the and has $\mathcal{O}(n)$- time complexity.

The brute-forcing approach will fail around when $n \approx 2^{80}$. There are better search algorithms for DLOG, the generic algorithms that work for any group;

Shank's Baby-Step Giant-Step method with $\mathcal{O}(\sqrt{n}\log n)$-time and $\mathcal{O}(\sqrt{n})$-space.
Pollard's $\rho$ method with $\mathcal{O}(\sqrt{n})$-time is improved version of Shank's method.
Pollard's $\lambda$ method (wild and tame kangoroos)
Adleman's index calculus with $\mathcal{O}(\exp(c \sqrt{\log n \log\log n}))$
Gordon's NFS algorithm with $\mathcal{O}(\exp(c(\log n)^{1/3}(\log\log(n)^{2/3})$-time

and

Pohlig–Hellman algorithm that is applicable when the order of the group is smooth. It has  $\mathcal O\left(\sum_i {e_i(\log n+\sqrt {p_i})}\right)$-time complexity where $\prod_i p_i^{e_i}$ is the prime factorization of group order $n$. To mitigate this attack this attack a prime order must be selected than is has same worst-case complexity as $\mathcal{O}(\sqrt{n}\log n)$-time.

DLog for Elliptic Curves (Additive): DLOG is also defined for Elliptic Curves, in which given a base point $G$ and another point $Q$ find $x$ such that $[x]G = Q$ where $$[x]P = \overbrace{G+\cdots+G}^{{x\hbox{ - }times}}$$

Dlog is not hard for every EC like curves with $|E(\mathbb{F}_q)|=q$. In Elliptic Curve Cryptography, we use curves where the Dlog is hard.

Some of the above generic algorithms, Pollard's $\rho$, Pollard's $\lambda$ also apply for DLog for Elliptic Curves, except index calculus-based algorithms and NFS. The records on finding DLog on EC mostly based on parallel Pollard's $\rho$.


AES-ECB known ciphertext/plaintext attack

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

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

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


Ensure Data Integrity In An ECDH Key Excange

1. Authentication

  then node 2 would know what the clients IP is

This statement is not necessarily true. If a certificate is given to a web site, then yes, IP or domain name will be known. But if your client is a person, then certificate can create some email address that can be without any meaning to the world.

2. Pre-shared secret

Use a pre-shared secret. For instance, you can use it for HMAC.

If the client has neither a certificate that you trust nor pre-shared secret, you cannot be sure whom are you communicating with: with your client or with a man in the middle.

Update

Key exchange is one of the most important and most complex questions in cryptography. There is no trivial solution.

A) Use secure channel for key exchange. You can exchange key via direct contact with the other party (not realistic), or somebody whom you trust carries the key from you to the other party, or you have a secure physical channel, etc. Here an asymmetric algo can be preferred, because the public key and thus the channel does not need to be confidential.

B) Use some chain of trust. If you trust to some CA (like Google) and trust its sub-CAs, then you can trust that the public key of the other party really belongs to it. If you trust... You know that Google Chrome distrusted certificates issued by Symantec & Co (Thawte, VeriSign, GeoTrust, ...). You heard about DigiNotar and Trustwave. E.g. Trustwave intentionally issued multiple certificates that enabled MITM. On the other side the number of correctly created certificates is estimated of about 99.995%. Besides certificate issuing there are other important aspects like trustworthiness of DNS.

Some may mention quantum approach. But it is actually requires on these two.

As you see, there is no easy solution.


4th Root of RSA Modulus Attack algorithm

It hold that $0\ge-\left({p-q\over2}\right)^2$. We add $\left({p+q\over2}\right)^2$ on both sides and use $N=\left({p+q\over2}\right)^2-\left({p-q\over2}\right)^2$ (hinted, and easily established from $N=p\,q$ ). We get $\left({p+q\over2}\right)^2\ge N$. From that, by taking the square root of both sides (which we can do since the quantities are non-negative), we get $\frac{p+q}{2}\ge\sqrt{N}$, QED.

The fun part is after this warmup..

The general idea is to search for $s={p+q\over2}$, by searching integers $s$ incrementally starting from $s_0=\left\lceil\,\sqrt N\,\right\rceil$, until $s^2-N$ is the square of some integer $t$; that is $\exists t\in\mathbb N$ with $t^2=s^2-N$, or equivalently $\sqrt{s^2-N}$ is an integer.

Notice that ${p+q\over2}$ is an integer when $N$ is an odd composite, and we just proved ${p+q\over2}\ge\sqrt N$, thus ${p+q\over2}\ge s_0$, thus the above strategy insures $s$ will ultimately reach $p+q\over2$. When that happens, we'll have $t={p-q\over2}$, and we'll thus be able to get $p=s+t$ and $q=s-t$, leading to a factorization of $N$ (perhaps partial if $N$ has more than two factors).

Speed depends on:

How many $s$ there are to test, that is how high $s$ will get over $s_0$. With a little algebra, an upper bound can be found by assuming $p-q\le2\sqrt{2}\sqrt[4]{N}$, which is how I read one of the hints; or it can be directly found an asymptotic bound using the assumption $p-q=O(\sqrt[4]{N})$.
How fast we can determine that $s^2-N$ is not a square (or better, summarily skip a sizable fraction of candidates for $s$); for example, in base $10$, squares never have their rightmost digits among $\{2,3,7,8\}$ and that helps get rid of some $s$ without computing a square root. However, such tweaks (many are possible) are not necessary to get the desired asymptotic bound, with polynomial of unspecified order.

This is known as the Fermat factorization algorithm.


Problem on Elliptic Curve Point Doubling

The point addition $P+Q$ and doubling $2P = P +P $ in Elliptic Curves $E$ are not just x,y coordinates in the Euclidean Plane that you can add the coordinates. One can find the rules in Wikipedia;

Point addition: With 2 distinct points, P and Q, addition is defined as the negation of the point resulting from the intersection of the curve, E, and the straight line defined by the points P and Q, giving the point, R.
Point doubling: Where the points P and Q, are coincident (at the same coordinates), addition is similar, except that there is no well-defined straight line through P and Q, so the operation is closed using limiting case, the tangent to the curve, E, at P and Q.

Given the Elliptic curve $E:y^2= x^3+a x + b$ and a point $P=(x_p,y_p)$ on the curve, the doubling $R=2P = P + P$ can be calculated by:
\begin{align}
\lambda &= \frac{3 x_p^2 + a }{2 y_p}\\
x_r &= \lambda^2 -2 x_p\\
y_r &= \lambda(x_p-x_r) - y_p
\end{align}
The curve is defined in modular arithmetic $\pmod{17}$, therefore convert $1/2$ into $2^{-1} \equiv 9 \bmod 17$ and find the inverse by extended GCD algorithm.
$\lambda = (3\cdot 5^2 +2)\cdot 9) \equiv 13 \bmod 17$
$x_r = \lambda^2 - 2 x_p  = (13^2  -10 ) \equiv 6 \bmod 17 $
$x_y = \lambda(x_p - x_r)-y_p =  13 \cdot ( 1 - 6) - 1 \equiv 3 \bmod 17$
$$(5,1) + (5,1) = (6,3)$$


Since N xor C reveals the first 64 bits of S, the secret cannot be reused. Also, a MITM attacker can observe the message sent from A to B then drop it. Then the protocol cannot restart with a new nonce. If you prefer a challenge-response protocol, maybe just use S to hash the nonce and send the result to the other party.


It's simple.  Lena is 512 x 512 pixels with a bit depth of 8.  So you simply export the raw image to a file that will be exactly 262,144 bytes long. It's critical that you export or save the image as a raw binary file, not one of those JPEGey things.  That won't work.

To determine the two chi values, you then consider the file as a series of consecutive individual bits, or as pairs of bits.  This will entail a load of bit shifting /masking operations in your favourite programming language.

A tip.  Install ent, and just run it twice against the encrypted Lena file.  Run one, use the -b option which will treat the file as a series of bits.  The output will produce a chi and p value.  Run again without the b option.  This will process the file as a series of 8 bit values.  If the encryption produces independent  (non correlated) bits, they can be lumped into four pair groups and treated as octets.  Assume the same 5% confidence value, and look at the returned chi value to see if it's acceptable. You'd expect  $219 \leq \chi^2 \leq 293$ for randomly distributed octets.

ent will also give you the Shannon entropy of the images for comparison with those in the paper.

Another tip.  Do not assume that a chi failure means the encryption fails.  Randomness is pesky and you have to try the test several times on repetitive images or keys.


What you want is a key derivation function (KDF).  Here's a fairly thorough list of some standardized ones.

Ps. The suggestion given by user1852723 to use HMAC, with your "seed" as the key and a counter (or other non-repeating sequence) as the input, more or less corresponds to the "Counter mode KDF" construction described in NIST SP 800-108, with HMAC as the underlying PRF.


Security of Fast Two-Party ECDSA Signing

In real life, $P_1$ of course does not abort randomly; this would make no sense. The idea is as follows. Assume that a cheating $P_2$ can forge a signature with probability $\epsilon$ when interacting to obtain $p(n)$ signatures are signed with the system. Now, if $P_2$ cheats then there is a first place where $P_1$ aborts. An adversary for ECDSA can simulate everything and guess where this first abort happens and will be correct with probability $1/p(n)$. This implies that the adversary for ECDSA can forge a signature with probability $\epsilon/p(n)$. Since ECDSA is assumed to be secure, this means that $\epsilon$ must be negligible.


Is this variant of Diffie-Hellman viable and quantum resilient?

Is this actually a viable method of key exchange?

No. An eavesdropper can find the integer $b$ chosen by Bob from $x$ (as sent by Alice) and $b'$ (as sent by Bob), and the equation $b'\,=\,b\,x\bmod 1$ (meaning $\exists d\in\mathbb Z,\ b'+d=b\,x$). The shared $k$ can then be determined from the $a'$ sent by Alice, just as Bob does.
If we take the numbers in the paper's example (section 5), given the first 14 decimals $B$ of $b'$ (out of the 61 sent by Bob) and the 24 first decimals $X$ of $x$ (out of about 71 received by Bob and 30 shown), we get $b$ as follows:

$B$ is the 14 first decimals of $b'$, thus $\big|B-10^{14}\,b'\big|<1$
$X$ is the 24 first decimals of $x$, thus $\big|X-10^{24}\,x\big|<1$
$b'+d=b\,x$ implies $10^{24}\,(b'+d)=10^{24}\,b\,x$
thus $10^{10}\,(10^{14}\,b')+10^{24}\,d=(10^{24}\,x)\,b$
thus $\big|10^{10}\,B+10^{24}\,d-X\,b\big|\le10^{10}$

One method to solve such Diophantine inequality for $b$ (we don't care for $d$) uses continued fractions¹. But we can be lazy and ask Wolfram in near-natural language
|10^10*62932060503117+10^24*d-693147180559945309417232*b|≤10^10 and b>0 Diophantine
and it gives us $b=6913952452$; or use Mathematica to the same effect, Try It Online!
B = 62932060503117;                 (* 14 first decimals of b' *)
X = 693147180559945309417232;       (* 24 first decimals of x  *)
Solve[Abs[10^10*B+10^24*d-X*b]≤10^10 && b>0 && b<10^11, {b,d}, Integers]
…
{{b -> 6913952452, d -> 4792386648}}

More generally, if $a$ and $b$ have $n$ digits, and we want the shared $k$ to agree over $m$ digits with residual odds of the contrary in the order of $10^{-j}/5$ (where that $/5$ assumes rounding to the nearest), then Alice and Bob should agree on $x$ over $2n+m+j$ digits, and send $a'$ and $b'$ over $n+m+j$ digits.
The paper's example targets $m=30$ shared digits in $k$, uses $j=21$ (thus almost always reaches its target), and $n=10$, which is small enough that brute force is usable to find $b$. But the attack above (or the explicit method¹) works in time only polynomial in the number of digits used. Try It Online! with $m=50$, $j=21$, $n=70$: it still takes under 1 second to recover $b$.
The paper should have been screened by the review process of a would-be scientific peer-reviewed journal on cryptography. I conclude Article Processing Charges do not ensure quality. I am not aware of similar mishaps in peer-reviewed publications of the IACR (thus excluding eprint), but that happens more than occasionally in many other publications. See Wikipedia's article on the publisher, and the publisher's response.

Is it really resilient to quantum computers?

In a sense yes for today's quantum computers, since they are unable to compute exact results on more than a few bits. In a distant future, perhaps no. That is: the scheme is not quantum-resilient. It's not even resistant to classical computer.

Is the $\bmod1$ calculation a known one-way/symmetrical function, and is it used elsewhere?

In cryptography, schemes that manipulate reals to a precision better than an FPU register are the exception rather than the norm, and always are internally implemented as integers divided by some integer scaling factor (often a power of a base). Therefore $\bmod1$ is implemented as modular reduction modulo the scaling factor.
Modular reduction modulo an integer is a common building block for one-way functions, such as (in Diffie-Hellman) $k\mapsto g^k\bmod p$ where $p$ is prime, $q=(p-1)/2$ is prime, and $g^q+1\bmod p=0$. But modular multiplication by a public constant (as used in the question's article) is not one-way.

Following the author's comment: the question, and this answer, assume $x$ is public. If $x$ is secret, the scheme is indeed less insecure, and even secure on first use of $x$ when the right parameterization is used. But with the parameterization in the example, we don't need $x$ to find the shared value². And even with good parameterization, if $x$ is reused, security quickly breaks down. The second part of the article's  “The security benefits from distributing $x$ via a secure channel, but this is not necessary” is untenable.

¹ It took me more time than I had hoped to reconstruct an explicit method:

Using continued fractions, write $\frac X{10^{24}}$ as the simplest fraction $\frac r s$ such that $\left\lfloor\frac{10^{24}\,r}s\right\rceil=X$. This is essentially the most compact representation of $x$ as an integer fraction giving it to 24 decimal places. Here $\frac r s=\frac{698526063389}{1007760087583}$
Round $\frac{s\,B}{10^{14}}$ (here 634204188043.9984…) to the nearest integer $t=\left\lfloor\frac{s\,B}{10^{14}}\right\rceil$.
Without proof: there remains to solve for $b$ the Diophantine equation $s\,d+t=r\,b$, here $1007760087583\,d+634204188044=698526063389\,b$
Reducing modulo $s$, we get $t\equiv r\,b\bmod s$, with $r$ and $s$ coprime by construction of $\frac r s$, thus $r^{-1}\,t\bmod s=b$ when $b<s$ (without proof: which holds with high probability when enough digits of $x$ are known in order for the scheme to work reliably). Here $b=6913952452$.

² Assume we have $a'$ and $b'$ to 61 digits as in the example, but not $x$. :

Using continued fraction, express what's known of $a'$ (61 digits each) as a reduced fraction $a'=\frac e f$ with $f^2<10^{61}$, same for $b'=\frac g h$.
From $a'+c=a\,x$ and $b'+d=b\,x$ with $0<x<1$, for at-most-10-digit $a$ and $b$, it holds the Diophantine inequality $\big|b\,h\,(e+c\,f)-a\,f\,(g+d\,h)\big|<2\cdot10^{10}$ with $0\le c\le a<10^{10}$, $0\le d\le b<10^{10}$
Reducing this $\bmod f$ and $\bmod h$, it comes that for some unknown integer $r$ with $\big|r\big|<2\cdot10^{10}$, it holds $a\,g\,f\equiv r\pmod h$ and $b\,e\,h\equiv-r\pmod f$.
With $\ell\gets\gcd(f,h)$, $f'\gets f/\ell$, $h'\gets h/\ell$, and $s$ defined as $r/\ell$, it comes that for some integer $s$ with $\big|r'\big|<2\cdot10^{10}/\ell$, it holds $a=((g\,f')^{-1}\,r'\bmod h')$ and $b=((-e\,h')^{-1}\,r'\bmod f')$.
With $g'\gets(g\,f')^{-1}\bmod h'$ and $e'\gets(-e\,h')^{-1}\bmod f'$, it comes $a=(g'\,r'\bmod h')$ and $b=(e'\,r'\bmod f')$.
This now can be solved by Mathematica, Try It Online!. This gives 4 possible values for the shared $k$, and 10 for $x$.


The security of a block cipher is, based on what we know, invariant to the permutation cycles of the S-box. This is because the values are always transformed (by a fixed function or a keyed function) before going through the S-box again in the next round. Furthermore, many S-boxes are functions not permutations (i.e., output size is different from input size), so the property does not apply.

The permutation cycles of the entire cipher (with respect to a fixed key) are of interest. I am aware of a number of papers that examine this for DES (see last paragraph of page 277 in Handbook of Applied Cryptography).

The AES S-box does have a design behind it, both in terms of the steps take to generate it and in terms of its structure with respect to linear/differential/algebraic attacks. If you maintained these properties and only modified the permutation cycles, the security should be equivalent.

There is some work on using permutation polynomials to create s-boxes that may have some further insight into whether it is generally a good or bad approach. However I am not familiar enough to comment.


Setting MAC field to all-zero to indicate unencrypted data

Yes, a MAC can of course have an all zero result. But that doesn't matter, because the chance of that happening should be the same as taking a random choice out of a set where each element has the same probability, i.e. has a uniform distribution.

So the chance of an all zero popping up should - in this case - be about $1$ in $2^{128}$, assuming of course that the message changes every time (without pre-knowledge the chance would be the same, but identical input will of course result in identical MAC-values, so there's that). Now that is the same chance of guessing an AES-128 key in one go, i.e. the chance that it will happen is negligible. So in practice your scheme could be used fine.

Remind yourself though that using magical values should be avoided as a general principle. Even worse is of course that you remove all security provided by the MAC if the message is not encrypted. The integrity and authenticity provided by the MAC have value for unencrypted messages as well.

So yeah, you could certainly use the scheme, but I would rather sacrifice any other bit for this. I would not call it good practice. I'd only use the scheme if there was no other bit to sacrifice (i.e. the protocol is already established and I now have to perform a hack to put in extra options).

[EDIT] Note that an adversary in a scheme with optional MAC can send you any (unencrypted) message. Generally we require a MAC to avoid that situation.


Attacking RSA signature verification that ignores padding

If you were using $e=3$, then there is a well known attack by Bleichenbacher that enables the trivial generation of a signature that passes verification. This attack was never published, but is described here. Note that this attack appeared in a real vulnerability in Kindle (and some versions of Android).

In any case, the attack does not work for $e=65536$. However, if your question is whether or not it's OK to use this, then it certainly is not. The existence of the $e=3$ attack should be enough to convince you of that. On the other hand, if your question is constructive to find an attack, then I don't know - but it's a great research question.


What is the importance of AES add round Key (K0)?

AES-128 consists of 10 rounds. Each round  includes a public permutation (consisting of the composition of public permutations SubByte ShiftRows MixColumns except for the last round where MixColumns is ommited), and secret tranformations AddRoundKey (consisting of a XOR with a key-dependent and round-dependent value) before the first round, in-between rounds, and after the last round. Therefore there are 11 AddRoundKey. The question asks: why the first AddRoundKey?
Because without the first AddRoundKey, the public permutation of the first round would operate on the plaintext, thus be of no cryptographic value in attacks involving known plaintext.
Consider the most basic attack: brute force key search with a  known plaintext/ciphertext pair. With the first AddRoundKey, the input of the first public transformation changes for each key, adversaries must compute that permutation for each key tested, and it's output is very different for each key tested. But without the first AddRoundKey, the output of the first public permutation is a constant that adversaries can compute once at negligible cost; essentially, one round of AES is wasted.

Addition: the last AddRoundKey is here for the same reason. And the last round's MixColumns is removed because, should it be present, it would be possible to exchange that last round's MixColumns and the last AddRoundKey (after a linear transformation of the last subkey), and then that last round's MixColumns would be a public permutation operating on ciphertext, thus of no cryptographic value.

Addition: I do not see any substance to a claim that "the first AddRoundKey helps in implementing the encryption recursively".


Replacing elliptic curve diffie-hellman primitive with elliptic curve cofactor diffie-hellman for specifc curves?

Just to close this question . Yes, both ( ECDH with cofactor) and (ECDH without cofactor)  give the same result if the cofactor of the curve is 1. After using another third party source I am getting the correct result. There was an issue in the code


Using enigma and missing one word/sentence

As long as the plaintext has some sort of recognizable structure, it wouldn't be that hard to identify where a letter has been omitted. Here's an example (generated using the default settings of this online Enigma simulator):

Plaintext:  THEQ UICK BROW NFOX JUMP SOVE RTHE LAZY DOG
Ciphertext: OPCI LLAZ FXLQ TDNL GGLE KDIZ OKQK GXIE ZKD

Suppose the 15th letter of the ciphertext (N) is omitted. This would result in the following decryption:

Ciphertext: OPCI LLAZ FXLQ TDLG GLEK DIZO KQKG XIEZ KD
Plaintext:  THEQ UICK BROW NFVH JAOW FSNA TPPT ESUW BM

Clearly there's something wrong after the word BROWN, so let's reset the machine to its initial settings and insert an additional X after this word in the ciphertext:

Ciphertext: OPCI LLAZ FXLQ TXDL GGLE KDIZ OKQK GXIE ZKD
Plaintext:  THEQ UICK BROW NHPX JUMP SOVE RTHE LAZY DOG

This is much better, but now we have the word HPX, which makes no sense. A consecutive run of unlikely characters suggests that we inserted the extra character in the wrong place.

Therefore, the F in the original plaintext was probably correct, and the middle word of the plaintext must be F.X (with the . representing a character that was lost in transmission). There aren't many words that fit this pattern, and it isn't hard to guess which one is correct.

Obviously this method would be harder to use if a message contains clusters of missed and/or incorrect characters. But in that case the wireless operator at the receiving end could just request a retransmission of the message. I don't see why they would have to wait 24 hours.


Let's split your question into two parts: first the length extension attack problem with Whirlpool, and next your HMAC tool idea.

1. Is whirlpool vulnerable to length extension attack?

Yes, Whirlpool by itself (as a plain hash, not HMAC) is indeed vulnerable to length extension attacks.

Besides Crypto.SE Q&As like “Understanding the length extension attack”, the SkullSecurity.org website offers an explanation in their article “Everything you need to know about hash length extension attacks”. Here's an excerpt:

  The attack

  An application is susceptible to a hash length extension attack if it prepends a secret value to a string, hashes it with a vulnerable algorithm, and entrusts the attacker with both the string and the hash, but not the secret. Then, the server relies on the secret to decide whether or not the data returned later is the same as the original data.

  It turns out, even though the attacker doesn't know the value of the prepended secret, he can still generate a valid hash for {secret || data || attacker_controlled_data}! This is done by simply picking up where the hashing algorithm left off; it turns out, 100% of the state needed to continue a hash is in the output of most hashing algorithms! We simply load that state into the appropriate hash structure and continue hashing.

  TL;DR: given a hash that is composed of a string with an unknown prefix, an attacker can append to the string and produce a new hash that still has the unknown prefix.

  Example

  Let's look at a step-by-step example. For this example:

let secret = "secret"
let data = "data"
let H = md5()
let signature = hash(secret || data) = 6036708eba0d11f6ef52ad44e8b74d5b
let append = "append"

  The server sends data and signature to the attacker. The attacker guesses that H is MD5 simply by its length (it's the most common 128-bit hashing algorithm), based on the source, or the application's specs, or any way they are able to.

  Knowing only data, H, and signature, the attacker's goal is to append append to data and generate a valid signature for the new data. And that's easy to do!

In that article, they also link to a tool which allows to practically do a length-extention attack on every algorithm you could wish for – including WHIRLPOOL.

The tool – coded in plain C – is available for free and hosted at Github under the name hash_extender. Quoting its description, hash_extender…

  … implements a length extension attack against every algorithm I could think of:

  MD4
  MD5
  RIPEMD-160
  SHA-0
  SHA-1
  SHA-256
  SHA-512
  WHIRLPOOL

  I'm more than happy to extend this to cover other hashing algorithms as well, provided they are "vulnerable" to this attack -- MD2, SHA-224, and SHA-384 are not. Please contact me if you have other candidates and I'll add them ASAP!

2. I am trying to build some HMAC for a program and consider using whirlpool to do so.

This again lifts the length extension attack problem described above, since a HMAC construction (which securely hashes data with a secret key) prevents length extension attacks. For details on how a HMAC construction achieves that, you can check the Crypto.SE Q&A “How does the secret key in an HMAC prevent modification of the HMAC?” which explains that HMACs were designed to void length extension attack issues.

When trying to attack a HMAC,

  …the attacker only controls variable-length input to the inner hash, not the outer hash…

So, the answer which practically considers your question title as well as your description is extended to:

Yes, Whirlpool by itself (as a plain hash, not HMAC) is indeed vulnerable to length extension attacks – but since you plan to use it in a HMAC construction (which prevents length extension attacks) you can safely ignore that attack vector. Yet, it should be noted that I'm assuming you implement the HMAC construction correctly.

TL;DR

Yes, Whirlpool as a plain hash is vulnerable to length extension attacks.
HMAC constructions prevent length extension attacks, which voids that problem.