texts:
In ECDSA, assume your public key is $Q=(x,y)$, then when performing the verification of any message leading to a null hash value (that is $H(M)=0$), the signature $(r,s)=(x,x)$ would always lead to a valid verification for that message, no matter what your public key is.

This is the case since upon verification you compute:

$e = \textrm{H}(m) =0$.
Let $z$ be the $L_n$ leftmost bits of $e$, so it's zero.
$w = s^{-1}=x^{-1}\bmod\,n$ by my choice of $s$.
$u_1 = zw\equiv 0\bmod\,n$ and $u_2 = rw=xw \equiv 1\bmod\,n$.
the curve point $$(x_1, y_1) = u_1 \times G + u_2 \times Q= 0 \times G + 1 \times Q=Q$$
The signature is valid if $r \equiv x_1 \pmod{n}$, invalid otherwise, but this is the case by choice of $r$.

I'm perfectly aware that the probability of finding a message $M$ hashing into $0$ is extremely low, let alone a useful message... But without going as far as considering some big companies with tons of computation power, the zero value might somehow happen for example because of targeted faults in the memory of the device or through some other means... Whatsoever it seems me to be an important value since it creates such a special case.

Yet, according to my reading of Sec1v2 and other standards concerning ECDSA, none consider this specific edge case.

I have done some tests with a few libraries, and at least OpenSSL, Go, and Crypto++ are completely falling for it. Only mbedTLS seems to reject it, and does so with an error "MBEDTLS_ERR_ECP_INVALID_KEY".

I know this does not imply much in term of practical security, but I believe this should still be considered in the frame of the so-called defense in depth, knowing such a special case exists.

Regarding signature generation, having $H(M)=0$ also has the consequence of rendering $s$ only dependent on $k^{-1}rd$, but this does not imply anything in term of key recovery as long as $k$ is a secret.

So, what should one do about this?
Should a library explicitly reject such a special case upon verification? If so, shall it reject the 0 value or signatures where $r=s$? In the later case, it would mean that signatures generated correctly with a null hash would still be verified correctly.

More generally, do you see any other implication of such a case? To which extent is a null hash something to be worried about for ECDSA?


texts: Can I create a random access CSPRNG from a hash?

texts:
Can I use a keyed hash of a counter as a secure CSPRNG?
E.g. 4th random block is Hash(4, seed)

If not, what are the possible attacks?


texts: Stripping off message authentication or signature

texts: If attackers can strip off RSA / EC / -DSA digital signature and conduct CCA on AES-CTR or CBC payload, why can't they do the same for AES-GCM?


texts: Is SRP-6a post-quantum secure? If it is not post-quantum secure, do any post-quantum secure alternatives similar to SRP-6a exist?


texts: Why perfect secrecy can be ensured when a plain message and a cipher-text based on one-time pad are correlated?

texts:
First, some well-known results are as follows.
For random variables $X$ and $Y$, we have
$$H(X,Y) \leq H(X) + H(Y).$$ The equality is achieved when $X$ and $Y$ are independent.

Second, in one-time pad, random variables $M$, $K$ and $C$ are used to denote a plain text, a private key and the codeword generated by $M \bigoplus K$ (modulo-2 operation), respectively. Note that $K$ is independent of $M$. We assume an eavesdropper also received the transmitted codeword $C$ through a public channel, but he does not know the key $K$.

Then my questions are as follows?

1) Are $M$ and $C$ correlated?
(The answer is "Yes" to me due to the post https://math.stackexchange.com/questions/1218305/if-x-and-y-are-correlated-random-varibales-and-z-is-independent-of-x-and-y-then )

2) If they are correlated, $H(M|C) < H(M)$ should be true according to the statements in the beginning. However, in one-time pad, perfect secrecy can be achieved, which means $H(M|C) = H(M)$ when $H(M) \leq H(K)$. Can anyone help me out of this confusion?

Thank you very much in advance.


texts: How to encypt/decrypt messages after ECDH key agreement

texts: I am using Diffie-Helman key exchange to generate the shared secret. But how will can a message be encrypted using this shared key?


texts: Use AES-256 Or AES-CTR-256 For One Block?

texts:
I am have one block of data to encrypt that is 32-bytes long. Is it better to use the AES-256 primitive for this single block (not a stream) or AES-256-CTR, and also would there be any cons or pros to using one and not the other such as to security or something else I am not thinking about.

This question relates to this question: AES-CTR-256 Sub Keys With Encrypted Sub Key Index

In relation I was wondering if I should just use the AES-256 to encrypt the sub-key with the master key instead of using the nonce and XOR operation, or maybe it would be better to use AES-256-CTR and use a nonce for the master key prefixed to the file.


texts: To what extent would Bitcoin be private without address reuse?

texts:
Let's say Bitcoin had these rules from the start:

An address with balance cannot more receive money
An address must use all its money in one transaction

This would prevent address re-use. To what extent would this make Bitcoin anonymous?


texts:
I am implementing TLS 1.2 and using cipher ECDHE_RSA_WITH_AES_128_GCM_SHA256

According to RFC 5346 Section 8.1 length of premaster secret will vary depending on key exchange method.

So, what is the size of premaster secret according to above key exchange method?


texts: Side-channel resistant discrete uniform sampling on $d\neq 2^t$ values?

texts:
Assume you have some source of $\mathsf{Bern}(1/2)$'s (probably some CSPRNG in practice). What is generally done to sample from $\mathsf{Unif}([d])$ in a side-channel resistant way (assuming $d$ isn't a power of 2)?

For the power of 2 case, it seems clear that you can generate $t = \log_2(d)$ random bits and interpret them as an integer. While I'm sure the implementation must be more careful than this, this seems algorithmicly rather straighforward.

For the non-power of 2 case, you could simply set $t = \lceil \log_2(d)\rceil$, then rejection-sample from $\mathsf{Unif}([2^t])$. This seems like it should be side-channel resistant as well (when you reject you leak information, but you also throw away the randomness the adversary knows information about).
The downside of this is that (in expectation) it requires (up to) twice as many random bits used, if $d = 2^t + 1$ for some $t$.
This will still be $O(\log_2(d))$ random bits, so asymptotically it's optimal, but it definitely feels like it could be improved.

So my question is essentially if anything better is known/used (either in the literature, or in practice).


texts: How to calculate a private key from public key on elliptic curve?

texts: Provided, that you have to multiply a well known G by the private key to obtain the public key, why not keep adding G to itself until you reach the public key. The private key should be the number of times you've added the G to itself. Is it correct? And if so - why isn't it feasible?


texts: Implementing MAC with PRF family $f$, why do we need $f_k$ to be invertible?

texts: As per the title, say we have $\text{MAC}(k,m) = (m,f_k(m))$ where $f$ is a PRF family and every function $f_k$ is PRP, where $f_k(m)$ and $f_k^{-1}(m)$ are efficiently computable. I proved that this scheme is secure, but I do not understand why do we need $f_k^{-1}(m)$ to be efficiently computable, my first thought was to use it to validate the tag by running the inverse on the tag and getting $m$ back, but since we also send $m$ with the tag, computing $f_k$ on $m$ could easily be done to verify the message, any hint would be appreciated.


texts:
My professor put this on the slides but gave us very little context. It is meant to be an overview of how it works at a high level.

I have a programming background and I get the general idea of attacks like Chosen Plaintext Attack. Be warned I am terrible at maths!

Request: I hope someone can walk through what this is doing step by step in English. Please refer to the lecture slide.

Other questions:

What does the '.' dot symbol mean in the ChosenPlaintext(.) part?
What is a and b storing?
If a=b goto ... is this checking length or if both are the same text?

What I think is happening:
It checks if chosen plaintext a is equal to b and if true then quit the program. Else it sets m to the chosen plaintext a. It uses ChosenPlaintext(m) to encrypt it and assign returned ciphertext to c. For some reason, it does XOR next but I am lost...

This slide came before, hopefully it provides better context:


texts: How can avalanche effect be calculated? I would in particular want to know what platform or IDE can be used to calculate the same?


texts: Definition of Short Authentication String

texts: I am studying for my cryptography final and I passed by the following term: short authentication string. Please, can anyone explain it to me, thank you very much.


texts: Finding a secret cipher given the key and known plaintext?

texts:
Let $x,y,k$ be plain text, cipher text and key respectively. Also suppose $\operatorname{Enc}$ is the algorithm of encryption for block cipher with size $n$. So we have
$$\operatorname{Enc}_k(x)=y$$

We know that if $x,y$ are given finding $k$ for big $n$ is so hard. Now we change the problem:

Let $k$(with size $l$) be given and $\operatorname{Enc}$ secret. We want to find the function for $\operatorname{Enc}$. At least how many $(x,y)$ are needed to find $\operatorname{Enc}$?


texts: Behavior of AES-CTR with 128-bit nonce and possible overflow

texts:
If I feed 128 bits of randomness into AES-CTR as its IV / nonce / initial counter, what will happen if I feed in a random 128-bit integer that overflows and wraps around?

I've written a test for this and found that at least some CTR implementations do the expected thing and wrap the entire uint128 around, but is it possible to guarantee this? Are there common implementations that will fail or do different and thus incompatible things here?

I guess what I'm asking is whether this is portable or not.


texts: Double discrete logarithm on elliptic curve

texts:
Background:

I am attempting to implement the paper Publicly Verifiable Secret Sharing. I managed to get it working using modular groups, but when I want to make it more efficient by transferring to elliptic curve groups, Section 3.1 in the paper gives me problems:

Let $p$ be a large prime.

$G$ is a group of order $p$

$g$ is a generator of $G$

$q = (p - 1)/2$ is prime.

$h$ $\epsilon$ $\Bbb Z_p^*$ is an element of order q.

The double discrete logarithm of $y$ to the bases $g$ and $h$ is defined as $x$ where:

$ y = g^{(h^x)} $

Question:

Implementing this double exponentiation is straightforward in modular groups since $h^x$ can be naturally interpreted as an integer. However, in the case of elliptic curves, $h^x$ is interpreted as the point $h$ added to itself $x$ times, resulting in curve point, $[x]h$. It is then unclear to me how to get $y = g^{(h^x)}$, knowing $g$, $h$ and $x$. To calculate a curve point to the power of another curve point does not seem possible to me.

The folklore is that any cryptographic scheme based on a modular multiplicative group can be translated to an additive curve group. However, I don't see how this case. Can this double exponentiation be done on an elliptic curve or is is only possible in modular groups?


texts: reducing false positives in searchable encryption

texts:
Practical techniques for searchable encryption proposed by Song et al. [1] have a false positive rate of $l/2^m$ where $l$ is left half of encrypted bits and $m$ is right half and $l+m=n$ where $n$ is number of bits of the word being encrypted. For getting clarity on these bits please refer the figure 3 in page 6. (paper).

Especially when the input domain of words being encrypted is not so random say serial numbers, sequence ids etc. the false positives are simply high.

Is there any subsequent work done or techniques available for reducing the false positive rate ?

[1] – Song, Dawn Xiaoding, David Wagner, and Adrian Perrig. "Practical techniques for searches on encrypted data." Security and Privacy, 2000. S&P 2000. Proceedings. 2000 IEEE Symposium on. IEEE, 2000.


texts: Signal Protocol Header key encryption initialization vector

texts:
In Signal Protocol when you use a Double Ratchet you have 2 options:

Normal encryption = header + ciphertext
Encrypted header encryption = encryptedHeader + ciphertext

The encrypted header encryption has the advantage of encrypting the public ratchet key pair and counter, this can also encrypt the message mac and possibly the ciphertext length encase needed over a network.

When encrypting a header you must have an initialization vector (aka IV) since the key will only change once receiving a new ratchet key pair (when moving a step in the DH ratchet (specified in the Double Ratchet documentation)).

You can read more about the function that header encryption must follow in DoubleRatchet - External Functions.

NOTES:

The header will be encrypted with "AES/CBC/PKCS5Padding" (in Java PKCS5Padding is actually PKCS7Padding) as specified in Java or in normal cryptography AES with CBC mode and PKCS7Padding as the padding
The ratchet public key is 32 bytes

From what I can think of I have 3 options for choosing the initialization vector now:

Generate a new 16 byte initialization vector and prepend it before the header
Take the first 14 bytes of the current ratchet public key (NOTE: the ratchet public key changes every DH ratchet step) and append the current counter as a short (NOTE: the counter increments every message and resets to 0 every DH ratchet step) which should generate a unique initialization vector, tho mostly predictable (NOTE: this is mostly predictable because this is considering if they actually have the ratchet public key and counter, with header encryption they are encrypted so they should be unknown to a malicious party)
Use the second option just with instead of taking the first 14 bytes of the ratchet public key taking for example the first 30 bytes (will result in 32 once appending the counter) or even the whole key.

So my question is, which should I choose?

Things to consider:

The first option gives a more random value, yet exposes it and also take 16 bytes more space.
The second option gives a less random value tho the first 14 bytes will still look random, the initialization vector is not exposed which possibly increases security and takes 16 bytes less space
Third option results in a bigger initialization vector making it more random


texts: Dividing elements in $R_q$ by $z$ in Grag-Gentry-Halevi (GGH) Graded Encoding Scheme

texts:
I'm trying to understand the GGH graded encoding scheme, but something there leaves me very confused and I can not figure out how to explain it:

Let $R := \mathbb{Z}[X]/(X^n+1)$, where $n$ is a power of $2$ (hence $X^n+1$ is irreducible in $\mathbb{Z}[X]$); $q := 2^a$ for a large enough $a$;
$R_q := R/qR$, i.e. $R_q = \mathbb{Z}_q[X]/(X^n+1)$.

In the scheme, we choose $z$ uniformly at random in $R_q$. Then the scheme uses this $z$ to divide other elements in $R_q$, like $[c/z]_q$. But is it correct? I believe $R_q$ is not field (it is not even integral domain) and so not every element there has it's multiplicative inverse.

Or maybe I misunderstood the notation?

Thank you for any advice.


texts: Understanding LFSR stream ciphers and the content scrambling system

texts:
I'm a little confused over how exactly Linear Feedback Shift Registers (LFSR) work, I kind of get it, but not really, can someone help me understand it? I know it XORs bits in a loop against some mask, how is the shuffling defined?

A content scrambling system is a synchronous stream cipher made from 2 LFSRs of different lengths, one with 17 bits and the other with 25 bits. If a 40 bit key is loaded into the LFSRs, 2 bytes into the first LFSR and 3 bytes into the second remaining bits in all set to 1. The outputs are combined to produce the keystream.

How would I go about finding the max period of each LFSR? Is it as simple as $2^d-1$ (simple ($2^{17})-1=131071$ and ($2^{25})-1=33554431$) or is it a little more complex?

Why does the content scrambling system use different LFSR lengths, why must it be 17 and 25 and not something different?

How would I go about brute forcing it, and what would the complexity of the brute force attack be?

If i simply XOR the two LFSR outputs, what would be the result be like (I'm assuming there would be some sort of way to identify information out of it)? Would a known plain text attack prove effective?


texts: What are cryptographic techniques that could be used so that if I wanna to enable a server to send message to certain nodes in a network with preserving the privacy location for them ??


texts: Can combining two secure block ciphers be insecure?

texts:
Let's say we have two secure block ciphers FOO and BAR. Will a new block cipher built by combining them into a single new block cipher result in any insecurity?
$$\begin{align}
\operatorname{BAZ}_K(x)&=\operatorname{FOO}_K(\operatorname{BAR}_K(x))\\
\operatorname{BAZ}^{-1}_K(x)&=\operatorname{BAR}^{-1}_K(\operatorname{FOO}^{-1}_K(x))
\end{align}
$$


texts: Security implications of not concatenating a 1 to the IV when using GCM

texts: When using GCM, The padding string $0^{31}||1$ is appended to the IV. I know that this is done to avoid the repetition of $E_K(0^n)$ which is used as key for the GHash. But what would be the security implications if the IV could be $0^n$, what concrete attacks would be possible then?


texts: How to decrypt c when phi(n) and e are not relatively prime

texts:
I have read multiple websites to see what would happen with RSA when $\phi(n)$ and $e$ are not relatively prime, but no one has discussed it.
Can someone explain how to decrypt $c$ if $\phi(n)$ and $e$ aren't relatively prime?


texts: Can elliptic curve point common factors be detected?

texts: Consider the two EC points $X=abG$ and $Y=bG$. Is it possible for someone to examine $X$ and $Y$ to determine if there is a common factor, as long as $a$ and $b$ are randomly chosen numbers between 0 and the size of the finite field? Even if the common factor $b$ cannot be determined, can it be determined if there is, or if there is likely to be a common factor? Assume the ed25519 curve is being used.


texts:
This was mentioned in a different question.
However Wikipedia states it is proven to be unsolvable.

So I would like to know what it is in this context and - since it is unsolvable - what the protocols trying to achieve it are actually doing.


texts: Are there any FHE-MPC schemes implemented?

texts: I want to know if there are any publicly available multiparty computation schemes derived from fully homomorphic encryption schemes. An example would be the implementation of this scheme https://eprint.iacr.org/2013/094.pdf.


texts: Is there a standard or recommended format for encrypted data, with algorithmic agility?

texts:
I am storing relatively small (from a few bytes to less than 50MB) amounts of encrypted data for an extended period. This data is encrypted using a custom tool that has already been in use for some time. I am reviewing the current implementation and am considering whether I need to make any changes. I must retain support for previously encrypted files and so (I think) must keep the leading Format ID to distinguish between formats. Beyond that, I am free to modify the configuration as I like.
If there is a standard or de facto format that would provide algorithmic agility, I would much prefer that to roll my own. Is there such a thing?
Alternatively, what standards/best practices apply to developing such a format? Are there any particular pitfalls I should bear in mind?
The existing format currently is as follows:
## File format

# +--------------------------------+
# |           Format ID            |  1 byte
# +--------------------------------+
# |        Unused (Legacy)         |  3 bytes
# +--------------------------------+
# |           Cipher ID            |  2 bytes
# +--------------------------------+
# |            HMAC ID             |  2 bytes
# +--------------------------------+
# |      Initialization Vector     |  16 bytes
# |                                |
# +--------------------------------+
# |           Key Salt             |  8 bytes
# +--------------------------------+
# |           HMAC Tag             |  Variable length, varies with
# ...                            ...  digest algorithm
# |                                |
# +---------------------------------
# |        Encrypted Data          |
# |                                |
# |                                |  Variable length
# ...                            ...
# |                                |
# +---------------------------------

Should the HMAC Tag cover just the encrypted data and the IV (that is what it does currently)? Is it desirable/practical to provide some integrity for the other parts of the header as well?


texts:
I am a bit confused about the knapsack implementation regarding the bits and block size for encryption.

In the example from this link (https://nrich.maths.org/2199), the knapsack size is 6 and the String that they encrypt has only 6-bits in 3 blocks.

My understanding is a Char can be represented by 7 to 8-bits (UTF-8) and the knapsack size must be at least of size 8 to encrypt one char. Meaning that if I want to use a knapsack for encryption/decryption I must use a knapsack size of 8. Is my understanding correct?


texts:
I would like to know how to store a sensitive file; a credential of sorts.  I want to password-protect it, obviously.  It would be appropriate - in my application - to prompt the user for the password each run.  There are proper apps - like SSH - that password-protect private keys and so on, and that's the model and best-practice I'd like to follow.

What is the best-practice for encrypting small files?  I'm thinking of generating a random key to encrypt the file with and using a block cipher.  And then encrypting this random key with the user's password, and trying to salt and stretch that password.

In the same way that storing password hashes is something you should turn to a proper 'stretching' function like bcrypt/scrypt/PBKDF2 (ideally via a library like Python's passlib) rather than rolling your own, are there proper algorithms and libraries for password-protecting files?


texts: Is a larger block size less secure against a brute-force known cipertext attack?

texts:
Suppose a ciphertext $c$ was encrypted from plaintext $m$, and we know something about the form of $m$; say, for example, that $m$ is English text.
We can attempt to brute-force $m$ from $c$ by computing $E^{-1}(c)$ for all possible encryption functions $E$ and discarding the values of $E^{-1}(c)$ which are not English text.
However, the probability of $E^{-1}(c)$ consisting entirely of English text (assuming $E$ behaves ''randomly'') decreases as a function of the block size. Hence, it seems that a larger block size results in fewer false positives.

Am I correct in saying that large block sizes are more susceptible to this kind of attack? Do we have to keep this in mind when designing encryption techniques, or are other factors (e.g. key length) more likely to be security bottlenecks?


texts: How to encrypt file with RSA and AES that anyone with RSA key can decrypt them?

texts: How to encrypt a file with RSA and AES-256 that anyone with RSA key can decrypt them?.


texts: Should HMAC-SHA3 be preferred over H(C(k,M))?

texts:
If I understand correctly SHA-3 (Keccak) is resistant against more attacks than SHA-2. This would make it possible - again if I understand correctly - to use SHA-3 with a simpler scheme than HMAC.

Would there still be a reason to use the HMAC construction with SHA-3? Would it be a better idea to simply use $H(C(k, M))$ where $H$ is simply SHA-3 and $C$ is a function to create a canonical representation (encoding) of the key $k$ and the message $M$ to set them apart?

Of course I imagine that HMAC-SHA3 will be used in the majority of protocols anyway as SHA-3 was created as a drop in replacement of SHA-2. But is there any security related reason to use HMAC-SHA3 over an (even) simpler scheme?


texts: Information-theoretically provable Privacy Amplification?

texts:
In Quantum Key Distribution, the distributed key is produced by Privacy Amplification (also known as key distillation). An ID Quantique whitepaper introduces it with a

  Rudimentary Privacy Amplification Protocol
  Let us consider a two-bit key shared by the emitter and the receiver and let us assume that it is 01. Let us further assume that the eavesdropper knows the first bit of the key but not the second one: 0?.
  The simplest privacy amplification protocol consists in calculating the sum, without carry, of the two bits and to use the resulting bit as the final key. The legitimate users obtain 0 + 1 = 1. The eavesdropper does not know the second bit. For him, this operation could be either 0 + 0 = 0 or 0 + 1 = 1. He has no way to decide which one is the correct one. Consequently, he does not have any knowledge on the final key. There is a cost. This privacy amplification protocol shortens the key by 50%. In practice, more efficient protocols have obviously been developed.

Updated formal definition: In this question, Privacy Amplification aims at deterministically producing as much as possible nearly secret uniformly random and independent bits, rigorously bounding the advantage any distinguisher may give, when given as input

$n$ partially secret bits, having been significantly and individually probed or/and influenced by an adversary, so that the remaining secret entropy is $\ge s\,n$ bit for some known $s\ll1$ (say $s=1/4$ );
and optionally, some extra public uniformly random bits, assumed independent including of the partially secret bits;
and optionally, as few as possible extra secret uniformly random bits, assumed independent including of the partially secret and extra public bits.

The classical cryptographer could use a hash and ignore the optional extras, but that relies on unproven mathematical hypothesis, that Quantum Cryptography aims at replacing with physical hypothesis. What provable methods does Information Theory bring to the rescue? Can we do without the optional extras?

Full disclosure: I'm trying to plug a hole at B.2 there.

Note: Extra public bits are used in Chi-Hang Fred Fung, Xiongfeng Ma, H. F. Chau Practical issues in quantum-key-distribution postprocessing (in Phys. Rev. A, 2010). Extra secret bits are a figment of my imagination.


texts: Building an LSFR Logical bit map using characteristic polynomials

texts:
How would one build an LSFR logical map, with a characteristic polynomial such as

$$P(x) = x^4 + x^3 + 1$$?
Also how would you interpret it, and what would you do to  do the reverse it in order to create a characteristic polynomial from an LSFR map? Thank you


texts: Differences in definitions of "Computational Special Soundness"

texts:
I am looking at Unruh's transform (ePrint 2014/587) and in particular the definition in §2.2 for computational special soundness in sigma protocols. Let $\cal{R} \subset \cal{X} \times \cal{Y}$ be some relation, with statements $x \in \cal{X}$ and witnesses $w \in \cal{Y}$, and $\cal{L}_{\cal{R}}$ the associated language.
For fun I have been thinking about building sigma protocols that do not satisfy (the ordinary notion of) special soundness – i.e. if given, from the ether, some statement $x$ and two accepting transcripts $(com, ch, resp), (com, ch', resp')$ with $ch \neq ch'$, I can efficiently extract a witness $w$ such that $(x, w) \in \cal{R}$ – and what conditions may still be satisfied.
What is not clear to me in Unruh's definition is whether the QPT adversary $A$ (with no input, it is written $A()$ in the probability) knows a priori witness statement pairs $(x, w)$.
The reason I am unsure is because in the definitions of completeness (above) and HVZK (below), we have $(x, w) \leftarrow A()$.
Trying to resolve this issue by finding a definition of computational special soundness elsewhere led me to the book of Boneh–Shoup, which defines it in §20.9, Question 20.3. In particular it is defined as no efficient adversary $A$ being able to generate two accepting transcripts with different challenges for some $x \not\in \cal{L}_{\cal{R}}$ (NB their statements are called $y$) with non negligible probability.
The two seem quantitatively different, as Unruh's definition allows for $x \in \cal{L}_{\cal{R}}$ and refers to the existence of an extractor.
What am I missing? Thanks.


texts: Small subgroup attack on Diffie-Hellman key exchange

texts:
Alice and Bob are using DHKE in the group $\mathbb{Z}_p^ * $, where $p = 1031 = 2 \cdot 5 \cdot 103 + 1$. Their generator $g = 2$, which generates a multiplicative group of order $515$ in $\mathbb{Z}_{1031}^ * $. This group has a subgroup consisting of $5$ elements $\{ 1,518,264 = {518^2},660 = {518^3},619 = {518^4}\} $. Eve uses this subgroup to find out DH keys exchanged by Alice and Bob. In one exchange, Alice sends ${2^a} = 919$ to Bob. Eve intercepts the message, raises $919$ to the power $103$ and gets $619\,\bmod \,1031$. Eve sends $A = 619$ to Bob. Bob replies by sending ${2^b} = 270$. Eve intercepts it, raises $270$ to the power $103$, gets $660\,\bmod \,1031$, and sends $B = 660$ to Alice. Eve now finds the integer value of DH key ${B^a} = {A^b}$ computed by Alice and Bob without knowledge of $a$ and $b$, and actually without any more computations modulo $1031$. Explain how this is possible, and give the value of the resulting DH key.

My solution:

Eve was smart enough to come up with a subgroup $S < \mathbb{Z}_{1031}^ * $ such that $\left| S \right| = 5$ and $S = \left\langle {518} \right\rangle $. By Lagrange theorem we know that all elements of $S$ must have an order $1$ or $5$. Thus it follows that $\left| 1 \right| = 1{\text{ and }}\left| {518} \right| = \left| {264} \right| = \left| {660} \right| = \left| {619} \right| = 5$. Furthermore, we know that $S = \left\langle {264,518,619,660} \right\rangle $.

Alice sends to Bob ${2^a} = 919$, when Eve stops the message she computes ${({2^a})^{103}} = {(919)^{103}} = 619 = {518^4}$ and hence Bob receives $619 = {518^4}$. Bob sends to Alice ${2^b} = 270$, when Eve stops the message she computes ${({2^b})^{103}} = {(270)^{103}} = 660 = {518^3}$ and hence Alice receives $660 = {518^3}$.

The value of the key is $$K = {B^a} = {660^a} = {518^{3a}} = {518^{4b}} = {619^b} = {A^b}$$Clearly the usage of much smaller subgroup with the following properties allow Eve to forge the message and limit a search domain to $5$ values. However, i do not understand how Eve can find the integer value of the key without knowing $a$ or $b$ and without more computations modulo $1031$.

For different values of $a$ and $b$ the generator of $S$ - $518$ will produce one of five possible values that will satisfy the equality. The only way i see Eve finds the key is by trying all five possible values (e.g small exhaustive search). In this way Eve does not need to do more computations modulo $1031$ as she knows the elements of $S$.

However the problem asks to give the value of the key. Does it mean that i have to try all $5$ values from $S$ or the key can be indeed determined uniquely without performing exhaustive search on $S$?


texts:
While reading "Certificateless Public Key Cryptography" by Author Sattam S. Al-Riyami and Kenneth G. Paterson, they have considered generation of private keys by a Key Generation Center (KGC). If the KGC gets compromised it will break security, so why should a KGC generate private keys.

Will it be possible that user will generate pair of public and private keys and for authenticity of public key only, we will use some trusted center?


texts: Probability of Repeated Encrypted Block In Output Feedback (OFB) Mode

texts:
Is there any probability/chances of repeated encrypted block in Output Feedback (OFB) mode?
Is there any existing documentation/studies about that? If it is existing, can you please provide me a link for that documentation, I want to analyze it carefully, I can't find some documentation about the probability of repeated encrypted block in OFB, maybe it is existing but it is hard to find.


texts: What is the meaning of IND-CCA secure under standard model?

texts:
I notice that in many research papers (viz. "Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption" by Cramer and Shoup) the authors showed that their cryptosystem is IND-CCA secure under standard model. What does it mean? What does an adversary have access to in a challenger-adversary game?

Actually, my aim is to get a clear idea on IND-CCA secure under standard model. I am confused on the statemant like "The given public key cryptosystem is IND-CCA secure under Diffie-Hellman assumption ". Is this statemant means that this particuler cryptosystem is IND-CCA secure under standard model?


texts: Why is proof-by-reduction needed (for Elgamal proof of security, for example)?

texts:
The textbook proof for Elgamal encryption basically reduces to the Decisional Diffie-Hellman assumption (DDH).

Elgamal:
$Gen(.): x \xleftarrow{R} \mathbb{Z}_p$; $Enc(m,g^x): r \xleftarrow{R} \mathbb{Z}_p, U= m.(g^x)^r, V = g^r$; $Dec(U,V,x): m = U/V^x$.

Suppose I prove the secure of Elgamal (in the CPA security model) as follows:

  Since $r$ is uniformly random, $(g^x)^r$ is also uniformly random. Thus, $m.(g^x)^r$ follows a uniform distribution. Given two message $m_0, m_1$ during the Challenge phase, the corresponding ciphertext $c_0$ and $c_1$ follow the same uniform distribution. Therefore, the advantage of the adversary is the same as distinguishing two identical distributions, which is 0.

Can someone tell me what is amiss in the proof above? Why is it (or isn't it) sufficient to show that the ciphertexts following a uniform distribution, i.e. indistinguishable from a truly random value?


texts: Risk of appending secret salt to plaintext prior to RSA encryption?

texts:
TL;DR

Will appending session id to a password prior an RSA encryption introduce vulnerability where an eavesdropper can collect multiple encrypted password ciphertext and perform cryptanalysis to obtain the password? (Session id is known to the server only and unique for each visitor)

Background story

I have a login form that encrypts passwords using client-side (Javascript) RSA encryption and sends the encrypted passwords to backend server (PHP) to be decrypted and then sent to be authenticated by an LDAP server. This is to prevent any eavesdroppers from snatching the passwords should they be sent in plaintexts.

However, I have a feeling that if there was indeed an eavesdropper, he/she does not even have to know the passwords as he/she can just forge a request using the encrypted passwords (i.e. replay attack).

So I'm planning to improve the scheme by prepending/appending users' session id to plain passwords before encrypting them on the client-side. That way, even if an eavesdropper forges a request using an encrypted password, the backend server can check if the session id in the decrypted string does not match with the attacker's session id and hence reject the login request.

However, I have a feeling that an eavesdropper that monitors a particular user's login requests can take multiple versions of the encrypted passwords and perform cryptanalysis to obtain the plain password, something that would not be possible if the encrypted passwords remain the same in all the requests (which in turn is susceptible to a replay attack).

Is my worry a valid concern?

N.B.: Assume that HTTPS/SSL is not an option for my case.


texts: On the Acceptability of a Naive Pseudo Random Number Generator

texts:
My question is probably both philosophical and technical.
Background
I was developing a CSPRNG, and I needed to shuffle the bits in one step in the middle of the algorithm - any naive shuffle would suffice.
I had this question in my mind:
Why would be any difference if one chooses to confine to a "shuffle" algorithm (see next) instead of my whole complicated algorithm? Which terrified me, to be honest.

The Naive Method
I created a pool of $10^6$ bits where the 1's count exactly 50% and distributed consecutively.
$1111......0000$
Then used the very simple Fisher–Yates shuffle Algorithm to shuffle the bits.

Results
Trying different seeds and sequence lengths, the above-mentioned naive method passed ALL NIST and DieHarder Tests, in addition to the Next Bit Test. It was even superior to the results of urandom and Mersenne Twister (I know that the latter is not CSPRNG but it's widely used as PRNG).

The Question
I believe that if anyone proposes the above naive shuffle algorithm even if supported by its excellent results in the literature, it will be immediately rejected (though I'm open to correction here).
Then the question that is confusing me is : Why? I mean "Why" on both ways:
Why such naive and simple thing is not appealing and Why would such naive and simple method pass all tests and even surpass urandom and MT algorithm on the basis of the aforementioned tests (which are extremely used as an evidence of the proposed algorithms in the literature).
What is the "real" compass?


texts: Shamir's Threshold Scheme (Theory Part, Need some help understanding a term that I can't find online)

texts: What does the max(S, n) part mean, and what am I supposed to do with it? I somewhat understand, but it is still confusing. I don't know what it exactly represents. Can you help me please?


texts: Use of randomness in an Elgamal like encryption

texts:
Suppose I have the following encryption scheme: for a message $m\in\mathbb{F}_p^*$, I generate the ciphertext = $(g^r,f^mh^r)$ where $g$ is the generator of a cyclic group $G$ of unknown order $n$ and $F$ is a cyclic subgroup of $G$ of order $p$ and $h=g^x$ where $x$ is the secret key.

Since $G$'s order is unknown we randomly generate $x$ from a sufficiently large set of numbers $\{0, \cdots, B\}$ where $B$ is an upper bound on $n$ that can be calculated for a $b$ bit security level and $B$ is chosen in way such that $g^x$ is indistinguishable from the uniform distribution in $G$ i.e. to ensure $g^x$ is a random element from $G$.

Now suppose we want to protect this scheme against generic discrete log attacks for 80 bits of security and in this case our $\log_2B\gg 160$. Also, for 80 bits security, our secret key $x$ has to be at least 160 bits as our generic discrete log attacks have a $\sqrt n$ complexity.

Question -- Because I only need $x$ to be of 160 bits, can I explicitly choose a random $x$ of 160 bits and disregard my theoretical bound $B$ which is huge in size. My reasoning is yes because I want to prevent an attack at 80 bit security level, all I need is $x$ to be 160 bits and I can ignore $B$. Is my reasoning valid? Also, some explanation would be great if I am wrong.


texts: Is it easy to factorize a number of the form $n = t^{2} \cdotp p$?

texts: Is it easy to factorize a number of the form $n = t^{2} \cdotp p$, where $t$ and $p$ are large primes?


texts:
Suppose I wrote a function $$(salt,IV ) = \text{keyIVGenerator}(passwd)$$ which generates a random salt of size 32-bytes and a random Initialisation Vector (IV) of size 16-bytes. Then, use a  Key Derivation Function (KDF) like PBKDF2 to generate a key of length 32 bytes (dkLen=32).
$$key = PBKDF2(password, salt, deLen)$$
I created a function  $$ c = encryption(key,data,IV)$$, assume that padding of data (using aes CBC) is correctly done and logic is right.
When I ask the user for encryption and data, I pass the password to the function $keyIVGenerator(passwd)$ to get the $IV,key$, and $passwd$ them to the $encryption(key,data,iv)$ along with data. The encryption works.
And now suppose I have to decrypt the data I will need to pass the same key as generated by PBKDF2 for encryption to decrypt my data. The iv was prepended to the ciphertext.
But what about the salt.
If I pass the password requested from the user to $keyIVGenerator(passwd)$ it will generate a new key with the new random salt, hence the data won't be decrypted.
Am I supposed to prepended my salt to the ciphertext too? Should I keep a database of salts?
How do I generate the same key from PBKDF2?


texts: Has a SHA256 output ever been found consisting entirely of the same character?

texts:
Is it possible to have an output consisting purely of one character and does this change the entropy of that output? (If that's even possible to ascertain.)

As an example, the Bitcoin cryptocurrency is slowly and inadvertently compiling a list of inputs which produce outputs with successively larger numbers of trailing zeros in its blockchain. Will these ever be used to study the SHA-256 algorithm?


texts: What is the prp-advantage of a $2^{80}$-time adversary attacking AES-256?

texts:
I am somewhat confused with something I read in Dan Boneh's slides discussing the advantage of a $2^{80}$-time adversary attacking AES-256; according to Boneh, the assumption is that this advantage is bounded by $2^{-40}$ (see slide 8 here or fast forward to 7:04' in the video here).

I have been looking to a few lecture notes (e.g., Goldwasser-Bellare, pg 72, section 5.5 at cseweb.ucsd.edu/~mihir/papers/gb.pdf) and books (e.g., Boneh-Shoup cryptobook draft 0.3 chapter 4, the katz-lindell book, or the handbook of applied cryptography chapter 7), but I am still unsure about this bound. It seems unrelated to quantum attacks on the key, which may justify a square root on $2^{80}$; however, an exhaustive search for AES-256 keys should take $2^{128}$ steps on a quantum computer.

In addition, it doesn't seem to be related to the birthday paradox either. Most birthday attack related bounds in the aforementioned references were linked to a mode of operation (for example, CTR-mode attacks related to the number of blocks encrypted under the same key), proofs related to PRFs, etc. What I find confusing is the connection between the time complexity of the adversary and the PRP advantage bound, as the attack that distinguishes the PRP from a truly random permutation is unclear.

Is the $2^{-40}$ advantage assumption accurate? If so, how is it explained? Why the adversary is getting this advantage after all?


texts:
I'm learning more about the Merkle–Damgård construction, including its "alternatives".

I think I know how the Wide Pipe construction works, but am confused about the different images being used online.

Wikipedia uses this one, which has two lines going through the compression function. However, this one, scroll down to "Alternatives to Merkle-Damgård" and this one, scroll down to "The Wide-Pipe Hash: A Modified MD Hash" use an image which has just 1 line going through.

Why do the images look that different? Is one or the other simply wrong, or is there something I'm missing?


texts: Require x of y possible passwords to decrypt

texts:
Is there a way to set up encryption so that a certian number (x) out of a total (y) number of users/passwords are required to do the decryption?

Background: This is mostly a thought experiment, and I don't have a realisitic real world application for it, although they may exist. I recall first getting the idea from an interview with Edward Snowden (Neil deGrasse Tysons podcast I beleive), but cannot find any follow information about the concept.

Hypothetical example 1: There are 3 "leaders" to a finctional technologically country. In order to start a war, 2 of them must agree and provide their crypto keys to decrypt the required commands/codes.

Hypotheical example 2: There are 435 congressmen in the USA. Sometime in the future, bills must be passed using cryptographic methods. 50% of them must provide their key/password in order to get the master key and pass a law.

Trivial Solution: For each combination users, encrypt the master decryption key in order (alphabetical by username). For the first example, there are only 3 combinations, and it is trivial to just encrypt the master key 3 different ways. Unfortunately this does not scale well. For the second example, 218 out of 435 gives us ~3*10^129. (For reference, there are 10^80 atoms in the universe.)

Is their a more programatic way to perform this type of encryption? The more I learn about crypto, the more I see amazing applications for reletively straightforward mathematical algorithms.


texts: Which assumption is stronger (p-BDHI) and DL?

texts:
(p-BDHI): p-Bilinear Diffie-Hellman inversion problem

Given $P,sP,s^2P,...,s^pP$. Find $e(P,P)^{\frac{1}{s}}$.

(DL): discrete logarithm problem

Given $P,sP$. Find $s$.

To break (p-BDHI), attacker needs to break DL.

I think the two assumptions have same-level hard problem.

No one is stronger than another. Is it right?


texts: Integrity protection in wireless sensor networks

texts:
I have done a lab about wireless sensor nodes and got in touch with encryption for the very first time. There are some questions on my sheet, especially on integrity protection (the attacker wants to tamper our data) which I wanted to ask about. I read some stuff but I don't feel so comfortable:
1) Why is a simple checksum or MD5 sum insufficient?

I guess because they are not secure anymore. In 2004 some researchers found out that there are 2 different messages with the same MD5 value and one can create more. Same is true for the checksum (?)

2) Is CBCMAC a good way to achieve integrity protection?

If I understood the wikipedia article right it is secure for fixed length messages, for arbitrary long messages it is not secure anymore.

3) Block ciphers are often fast and readily available. When comparing HMAC
and CMAC, which do you suspect will work better in a WSN scenario? What
are the differences between them?

The differences are quite crucial: HMAC uses hash functions for encrypting and CMAC block ciphers. But I don't know which one is more suited in a WSN. As we have very limited resources one should maybe choose the one which "costs" less in terms of energy?

4) Is it a good idea to use the same key for both encryption and the MAC
function?

No it is not, in the CBC-MAC article wikipedia shows a big problem if you use the same key.

5) Are there ways to combine encryption and itegrity protection? Name at
least two examples. Is a single key sufficient in these cases? Do different
approaches differ with respect to their performance characteristics? Will
such an approach be usually faster, slower or equal to doing encryption and
MAC calculation as separate steps?

I guess this question is about authenticated encryption. The wikipedia article (http://en.wikipedia.org/wiki/Authenticated_encryption) is quite short and I can't find many information about these questions ...

I am thankful for any help


texts: Ideal passphrase length: old diceware method (5 words) vs. your Bitcoin wallet.dat passphrase lenght (8 words) and doubling passwords?

texts:
I made a cool 5 word passphrase back then using the old Diceware method and use it as a master password. The question is as computing power increases will we need to add more and more words to our passphrases which we will eventually forget? I'm in my mid 30s, will passphrases be enough in my lifetime? :) So back then, Diceware suggested just 5 words, not the original Bitcoin QT client recommends 8 words. Will theoriginal 5 words from the Diceware age will serve me in the Bitcoin age?

I don't really want to mess around with a Yubikey. Heck, I Googled it and didn't really managed to find out what it is, what it does. Maybe I'm not the target market. I'm just a simple user. Carrying around a Yubikey would also be a red flag in my eyes. He has secrets!

How effective is doubling a passphrase? Like I have now [passphrase] and simply doule it: [passphrase][passphrase]. So I don't really have more stuff to remember, just more stuff to type. That might serve me for a time.

Oh, another interesting question as well: let's say I use one exact password on many similar forum pages. Will this generate the exact same hashes if they use the same forum engine? I know, you can't recover the password from the hash, but they may find same hash = same guy, right?

Psl. form your answers in a newbie language, thank you!


texts: Is .NET DESCryptoServiceProvider secure in this case?

texts:
I have the following piece of .NET code (see below). I know that DES is not quite secure, I saw that MSDN does not recommend using DES, only for compatibility with legacy programs. I also saw that some people say that IV has to be regenerated every time new message is encrypted.

Q: How secure is the code? Assuming attacker has several hundred messages and corresponding ciphers (and can get more), how easy to break this and find key/IV?. How could it be done? But most importantly, how it could be made secure? Will change to AES help?
I'm a beginner and any help or references are very appreciated.

internal static class Encryptor
{
  private static readonly byte[] Key = { *** };
  private static readonly byte[] Iv = { *** };

  internal static String Encrypt(string source)
  {
    var des = new DESCryptoServiceProvider();
    var enc = des.CreateEncryptor(Key, Iv);
    var b = Encoding.ASCII.GetBytes(source);
    var encId = enc.TransformFinalBlock(b, 0, b.Length);
    return Convert.ToBase64String(encId);
  }

  internal static string Decrypt(string encrypted)
  {
    var des = new DESCryptoServiceProvider();
    var dec = des.CreateDecryptor(Key, Iv);
    var b = Convert.FromBase64String(encrypted);
    var decId = dec.TransformFinalBlock(b, 0, b.Length);
    return Encoding.ASCII.GetString(decId);
  }
}


texts:
As you may already know, proofs of retrievability (PoR) can be constructed using MACs, Signatures (as stated here) or Merkle tree (like this).
The PoRs that are based on MACs or signatures usually use the notion of extractability. Informally, it states that if a prover can convince the verifier (with a high probability), then the prover must know the file. So there exists an extractor that can interact with the prover and after a polynomial number of iterations, it can extract the full file.
However, I have not seen any Merkle tree-based PoR that uses any notion of extractability.
Question: Can Merkle tree-based PoRs also support extractability too?


texts: Is there specific name for simple XOR with ADD/SUB encoding?

texts:
Several years ago a group of malware authors began using code like this:

for (j = 0; j < length; j++)
  ptr[j] = (ptr[j] ^ VALUEA) - VALUEB;

for encoding, and this to decode

for (j = 0; j < length; j++)
 ptr[j] = (ptr[j] + VALUEB) ^ VALUEA;

I've recently seen this pop up in seemingly legitimate software. This leads me to believe that there is a source for this type of encoding somewhere in the wild. I was wondering if there is a specific name for this type of encoding?


texts: multiple keys via HKDF - whats better, one or two applications of HKDF-extract

texts:
Assume for the sake of the question that I have two variable-length bit strings, each with 128 bit cryptographic randomness, and I want to extract two 128 bit keys via HKDF-SHA256.

Which alternative is better (if any), and why?

Use a single HKDF-extract on the concatenation of the two strings, and two HKDF-expands with different info strings to get two 128 bit keys.
Use two HKDF-extract operations, one for each bit string, and use a single HKDF-expand on each to get two 128 bit keys.

Or in other words, is it better to HKDF-extract on a longer IKM string and use multiple HKDF-expands, or is it better to use HKDF on independent but shorter IKMs.

My intuition tells me that, if my randomness strings are really as good as I claim, then two independent HKDF extracts are better, but using a single one on the concatenation is, in practice, just as safe, and safer if my input randomness is not actually as good as assumed, so two HKDFs might be more robust in practice.


texts:
I have two devices that use a PSK. One is embedded and extremely resource confined. I'm already using ChaCha20-Poly1305 so it would be "free" to reuse this. There is no transport encryption layer, all clear and has middlemen.
I want to establish a randomvalue/salt/kdf-base and send this to the other device on authentication so that I'm never actually using my PSK directly. Both sides know the PSK, and use this modifier to alter their stored key, and use a common derivative for packets going forward.
My plan was to use some KDF to modify my key into a temporary session key.
Is it satisfactory to use my existing AEAD like this:
nonce: the generated salt
payload: empty
additional data: empty (OR a flag of key type I want, NIST 800-108)
key: my 16Byte PSK
tag: The 16Bytes I will use as this session's temporary key

What I FEEL like this is doing is giving me a tag that will be crypto secure to prevent leakage of my real PSK, and the salt will be OK to use here as well as send over the wire so the other side can do the same thing and evaluate the auth packets going forward.
Is this at all legitimate?


texts: How and why can a decryption program tell me that a key is incorrect?

texts:
I have noticed that some programs used for file encryption will tell you if an entered key is wrong when you try to decrypt. It seems (to me at least) that this would mean that the key somehow is written into the encrypted file. And the algorithms that I know of will produce an output even if the key is wrong.

How does one built into an algorithm this type of validation of a key? Is it just a matter of encrypting the key with the original text?
Is this a security problem?


texts: Which is the most overall 'compatible' encryption type?

texts:
What is the "MP3" of encryption formats today, which hopefully will make it easy and compatible to send to other recipients (not via e-mail), without them having to download and learn a software suite just to unlock what I sent them?

I work commercially and a part of it means sending people the end result files (usually multimedia files on the larger side). I do not work for a steady number of clients, so I need to deliver to all kinds of people where neither side knows in advance about how we prefer things done.
Most people I encounter in work aren't tech savvy when it comes to secure file transfers, and many express loud irritation from having to 'unlock' transferred files through some process they've never even encountered before. Their emotions about this tends to associate with me, as a content-delivery service, which might hurt business in the long run. But customers absolutely do want the files delivered 'securely'. That irritation, and wish for safety, are contradiction of course, but you wouldn't want to be the one to tell them that.

Some have also found their holy graal, in using AES256 or PGP or some other fairly known method, and here I come with something that doesn't correspond to that. Or, in some cases we both may be accustomed to 3DES encryption but we use different software to encrypt/decrypt, meaning my 3DES encryption won't unlock through the other guys' software even though it is the same basic encryption formula. Or the software needed to decrypt isn't available on the other person's platform.
People might also be in contact with other people who delivers files to them, meaning in the end they need to have multiple software suites installed and learned just to deal with all types of different encryptions and solutions. Sometimes topped off with a short temper.

Therefore I'm looking for advice/opinions about the probably most 'overall compatible' way of locking medium to large size files for sending over the internet, which might reduce the need for someone to adapt to me, or me to him/her. MP3 files can be used by virtually everybody. What is the MP3 of encryption, today?

Thank you for any thoughts and/or tips


texts:
Starting from a known CRC result(let's call it CRC1), could I undo the CRC operations for last N bits, so I could obtain the CRC (let's call it CRC2) of the message sequence without the last N bits.
$$
M(x) - message \\ M = \{M1,LastBits\} \\CRC_1=CRC\{M\}\\CRC_2=CRC\{M_1\}
$$
Does a function F() exist for which:
$$F(CRC_1,LastBits) = CRC_2$$

My hunch would be that such a function which would unrewind the last N CRC steps, would have 2N possible solutions.


texts: How much entropy is lost via hashing when you add known or low entropy data?

texts:
(I updated the title, as I think there was some confusion as to the question)

Here's the question:

For example, if I have a bit stream that is 64K bytes long and there is about 16 *8 bits worth of entropy randomly dispersed in that byte stream, so I have 16*8 bits worth of entropy.

However, if I SHA256 that byte stream, I will now only have 32 bytes total rather than 64K bytes.

Some information has been lost of course, but perhaps all of the entropy is retained?

Another way of looking at the question, is the entropy of SHA256(10GB with 16 bytes of entropy) equal to SHA256(16 bytes with 16 bytes of entropy) and if not, how much exactly has been lost?

I'm having a hard time finding any literature which estimates entropy loss, just a lot of hand waving by various crypto engineers that it's all good.

Here's an algorithmic way of looking at it:

#!/bin/sh
HASHV=`echo <random secret> | sha256`
echo $HASHV
while(true) ;
do
HASHV=`echo "$HASHV 00000000000000000000000000000000" | sha256`
echo $HASHV
done

Will the entropy of HASHV decrease over time?

Anyone got anything specific? (refs to papers, books, etc are grand)

Relevant questions:

What happens to the entropy of a password when you hash it?
Entropy of system data - use all and hash, or trim least significant bits?


texts: Why would an Initialization Vector be supplied externally?

texts:
My software uses a 3rd party encryption appliance. One of the capabilities they allow is for the client software to supply an IV while doing CBC encryption.

Why would they not generate a random number on their own to use as an IV?

What is the advantage of letting the client specify an IV?  I can only think of disadvantages, such as people supplying an insufficiently random number over a public network.


texts: Using a Non-Random IV with modes other than CBC

texts: The weakness CWE-329 is an interesting problem with CBC mode.  However, does this same weakness affect the other modes of operation that rely upon an IV such as: PCBC, CFB and OFB?  My gut feeling is, YES.  I am wondering if there a consensus on this topic?  Or is there a possible explanation of why its not a weakness.


texts: why do we asume that in the registration process communication is over the secure channel?

texts:
I was reading some research papers and saw that in Registration phase/process it is always assumed that communication is over the secure/private channel, whereas, all of the phases communication is happening over the public/open channel. What is the reason for this? on the basis of which parameter! we assume that the channel is secure/private insecure/public?
Thanks in advance.


texts: Can I increase strength of ECB by decorrelating input data with compression

texts:
I know that ECB block cipher mode is the weakest method of encryption because repetitions in input data with a stride of a block size lead to repetitions in output data.

However, as I may consider, elimination of repetitiveness should give a stronger result like for other modes (CBC, etc.). In addition, I know that compression algorithms are just designed specially for searching and removing certain types of correlations.

Let's consider input data are compressed using DEFLATE algorithm via zlib 1.2.11 with the highest compression level possible (9). How does such an approach increases the strength of ECB?

Update: My goal is to increase encryption speed by parallelization. I receive UTF-8 texts already deflated as specified in the previous paragraph, encrypt it with a user-supplied key, and put it to cache storage in a user folder.


texts:
I have some encoded strings which are probably encoded in a base64-variant - except that there aren't only 64 chars, but all the (printable) ASCII chars between 33 and 126 (0x21 to 0x7E).

I've searched for other base64-variants but only found variants like base85 which excludes some characters that may cause problems.

But in my case, the string also contains those characters like ` (backtick), {, }, [, and all the others. Every printable ASCII char.

Here's an example of one of the encoded strings:

  9xt3v}"&"z-&{Im!0{&|"xxw-N@[*;-f>6&II"pri:X>#[q$l82q_>QRQPg8pro6

Any way to decode such a string without knowing what encoding was used? Does anybody know about an encoding like base64 which uses every printable ASCII char?


texts:
In this paper they change the $AES$ S-box to a uniformly random one and answer the questions:

How does the security of AES change when the S-box is changed by a secret S-box?
Would it be safe to reduce the number of rounds?

I have tried reading the paper but there are some things I do not understand.

Are the S-boxes they are considering just random permutations of bytes that fit into an $8 \times 8$ table? How might they have chosen all the entries to get the S-box?
Are they choosing a random S-box and then leaving it unchanged thereafter?
In Section $3.1$ they state differential cryptanalysis will not pose a threat to variants of $AES$ where the S-box is replaced by a randomly chosen $8$-bit box. This is confusing. Do they mean one $8$-bit element in the S-box? I thought the S-box was $256$-bit, not $8$.
Still referring to Section $3.1$. If a random S-box is secure against DCA and LCA, why make such an effort to design the one currently in use?
How does a random S-box cause the secret information to go from $128$ to $256$ bits (depending on the key size) to $1812$ to $1940$. I understand there is now more secret information owing to the secret S-box but I cannot see where these numbers ($1812$ to $1940$) come from.


texts: What are good sources for properly learning cryptography for a mathematician?

texts:
I'm a pure mathematics student(currently in a Msc program) looking to get into cryptography. I imagine most "regular" introductory books on cryptography would avoid being too heavy on mathematical details due to the target audience. So I'd like to ask, if someone is perhaps able to recommend good books that provide an introduction to cryptography for someone rather unfamiliar with it, but having all the neccessary mathematical background to understand full details and justifications of the algorithms etc.

Edit: I'm aware that I can't possibly know  every theorem etc. involved, but I think it's safe to assume that I should be able to lookup any such additional details in reasonable time, while going through the book.


texts: AES MDS matrix: can we maintain security if we change the arrangement of elements in the matrix?

texts:
Apologies for 'unclear' question. And, 'yes' it is similar to an earlier one. I hope this is clearer.

AES uses the matrix below for the mix columns:

Would security be affected if the columns (or rows) were swapped around?
For example, if the first and second column were swapped to give:

Would this matrix be just as secure for the mix columns?


texts: Attacking a cipher, not knowing what the plaintext should look like – how do you know you’ve successfully decrypted the ciphertext?

texts:
I have thought hard at the risks of data being cracked, it seems to me that the biggest risk is still down to absolute security of the key.  On the presumption that the key will be kept secure then:

When hacking data how do you decide when you have successfully
decrypted it without knowing roughly what it was it the first place?
If it was a text document would you need to know what language it
was in?
Is it worth the minimal effort of making the users key more complex
before using it to encrypt the data?

OK, I am very definitely not a mathematician, self evident I guess.  I am using a library (Lockbox 3, https://sourceforge.net/projects/tplockbox) for the en/decryption and so am dependant upon the implementation being rock solid, another potential hole but I am casting no aspersions on the developers.

If one was attempting to crack the data are there mathematical mechanisms which can be used to decrypt without know anything about the data?  I'm not asking for an algorithm, a yes or no will do.

I am asking for a complex subject to be made simple, however I am only after broad answers.


texts: Does anyone sell a proprietary symmetric encryption alogirthm?

texts: I know that the majority of people use standardized encryption ciphers such as AES-256, and for good reason.  But what I want to know is if anyone has come across a company or organization that is selling their own proprietary symmetric encryption algorithm.  I'm doing research on this specific use case and would appreciate some help.


texts: What are the consequences of Diffie Hellman problem in P?

texts:
Computational Diffie Hellman problem wants to know $g^{ab}$ given $g^a$, $g^b$ and $g$ while the discrete logarithm problem wants to know $x$ from $g^x$ and $g$.
The latter resolvable in polynomial-time implies the former as well but a converse result is not known.
What are the consequences to cryptography if Diffie-Hellman is breakable but an algorithm for discrete logarithm is unclear?


texts: Stream cipher with an additional integrity stream?

texts:
I want to use a stream cipher to encrypt a continuous bitstream. Additional to that, I want to generate an additional stream to guarantee the integrity of the ciphertext.

stream a: ciphertext.
stream b: integrity check on stream a.

I am aware of authenticated encryption where the MAC can be accumulated and sent. I want to avoid that.

Is it possible to do this by encrypting the same plaintext using a different algorithm, key or iv? Will that actually protect against say bit-flip attacks? Does it cause any vulnerabilities?

Is there a better (preferably cheaper) way to do this?

Note that this has to be done in hardware and I am extremely limited on energy so I can't add any sort of control logic.


texts: Is there a way to easily encode a message without a computer on either end?

texts: I enjoy making notes and passing them to my friends, and I also like making them encrypted for no reason. My friends enjoy it too, but it's a bit annoying to use the Caesar cipher for everything because its repetitive and takes forever. Is there a better pen-and-paper way of encrypting messages?


texts: Is there a reduction of security if I XOR Pkcs5S2 and SecureRandom?

texts:
I'm using this codereview sample to encrypt data. I would like to provide hardware protected encryption and a user password as the key.

Is it acceptable to XOR the KDF Pkcs5S2 in Bouncy Castle with a device generated random key?

Is the resulting XOR key more secure than the KDF output?

*note the BouncyCastle PKCS5S2 implementation uses SHA1 as the HMAC calculation function if that matters.


texts:
MD5 is considered broken and SHA-1 is closely following, but HMACs built around either are still considered relatively secure. It makes me wonder if MD5 and SHA-1 HMACs can be used as secure hashes.

Settle on some constant $C$ that will serve the role of $K$.
Define a new hash algorithm as $H_C(x)=HMAC(C, x)$.

Could this work?


texts: Plain RSA with $3$ primes, find all integers $x$ so that $x$ is equal to $y$ when $y= e_K(x) = x^{b} \bmod n$

texts:
I'm using the notation from the book: Cryptography: Theory and Practice, Third Edition.
I have a cryptosystem with the following information:
$n = p_1 p_2 p_3$ and integer $x$ is encrypted using $y = e_K(x) =  x^b$ $mod$ $n$ and the decryption is $x = d_K(y) =  y^a \bmod n$
when $ab\equiv 1 \pmod{\varphi(n)}$
$n=231$, so: $p_1 = 11$, $p_2 = 7$, $p_3 = 3$
I want to find all $x$ so $x= e_K(x) =  x^b \bmod{231}$
I tried this:
$x^b-x \equiv 0 \pmod{231}$
$x(x^{b-1}-1) \equiv 0 \pmod{231}$
$x = 0$, $x = 1$ are solutions, to find the rest:
$\varphi(231)=120$ so $ab\equiv 1\pmod{120}$ but I don't know how to continue.
Since $120=2^{3}\cdot3\cdot5$ so $2\nmid{b}$ and $3\nmid{b}$ and $5\nmid{b}$
by following the RSA page from wikipedia: key generation:
$\lambda (231)=30$, so $1 \lt b \lt 30 $, the only integers that left from $1, 2, \ldots, 30$ are primes. then using Fermat's little theorem implies that for any integer $a$: $$a^{p} \equiv a\pmod p$$ so,
I tried to check CRT, CRT implies that $e_K(x) = x$ iff $x^b \equiv x \pmod{p_i}$ for $i=1,2,3$.
But I still don't know how to continue.
Thanks.


texts: Where is my private key stored when I communicate to a website that uses SSL/TLS?

texts: If I communicate with a website that uses SSL/TLS, my browser will generate a private key. Would the browser store that key on the hard disk or would store just it in the RAM?


texts:
Looking at RFC4253, I came across the notion that the MAC is applied the encoded packet concatenated with a sequence number which acts as a counter.

However, I couldn't find any information on how that sequence number is validated. What happens if some messages get dropped or corrupted during transit?

Also, when do SSH connections get dropped? As in, decryption failure, MAC verification failure, etc.


texts: How long does it take to brute force Blowfish-448?

texts:
I am conducting an investigation on the efficiency of AES and Blowfish with regards to memory when encrypting data of varying sizes.

I open my essay with an introduction as to what encryption is and the two algorithms I will be discussing.

I have mentioned that AES-256 as $2^{256}$ possible key combinations, and I would like to know how many Blowfish-448 has?


texts: Verify the discrete log of ECDSA is in range

texts: Is it possible to verify the discrete log in elliptic curve is within range without uncovering it? I need to verify that $x$ is within $1$, $2^{64}$ for $xG=P$.


texts: Convert sr25519 key pair to Curve25519 key pair

texts:
I'm trying to implement public key encryption that support key pairs generated by different libraries:

Curve25519 - libsodium cryptoBoxKeypair()
Ed25519 - Google Tink Ed25519Sign.KeyPair.newKeyPair()
sr25519 - Polkadot Schnorrkel over Ristretto

I'm using libsodium cryptoBoxSealOpenEasy() for encryption that is works, obviously, with Curve25519 and with Ed25519 after conversion with libsodium convertKeyPairEd25519ToCurve25519(). But I'm stuck with sr25519 - don't know how to convert it to Curve25519.


texts: Pseudorandomness of ring learning with errors

texts:
My question is in Ring Learning with Errors, let $a(x)\in \mathbb{Z}_q(x)/(X^n+1)$ where $n$  is a power of $2$, be a random polynomial, $s(x),e(x)\in \mathbb{Z}_q(x)/(X^n+1)$ are the secret and error polynomial respectively with co-efficients sampled from a discrete Gaussian distribution $D_\sigma$. Now, the decisional hardness of RLWE says that the samples $a(x)\cdot s(x) + e(x)$ are indistinguishable from a random polynomial $u(x)\in \mathbb{Z}_q(x)/(X^n+1)$.

Now, my question is whether the polynomial $a(x)\cdot s(x)$ $i.e$ the RLWE sample without error will be polynomially indistinguishable from a random string? As far as I can think, the error polynomial $e(x)$ is only used for the hardness of the problem. Does it also contribute to the polynomial indistinguishability of the samples?

The reason I am asking this question is that, recently I found a new problem LWR in these papers Banerjee et al., Alwen et al Bogdanov et al. which removes the error but introduces an error with rounding each co-efficient of $a(x)\cdot s(x)$, $\lfloor p/q(.)\rceil : \mathbb{Z}_q\rightarrow \mathbb{Z}_p$. They have gone great length to prove the computational indistinguishability of the LWR samples. The computational indistinguishability of RLWR is not proven yet. if $a(x)\cdot s(x)$ is computationally indistinguishable from a random polynomial in $\mathbb{Z}_q$ then can't we say $\lfloor p/q(a(x)\cdot s(x))\rceil$ is also computationally indistinguishable from a random polynomial in $\mathbb{Z}_p/(X^n+1)$ if $p|q$


texts: Probabilistic padding to avoid Håstad’s Broadcast Attack

texts: Can someone explain why probabilistic padding like OAEP is particularly useful for avoiding Håstad’s Broadcast Attack? I don't really get the reason why.


texts: Deciphering a substitution cipher if frequency analysis doesn't work (hypothetically)

texts:
If a text ciphered by substitution is in a artificial language with equal frequency distribution of characters, and perhaps 2 or 3-grams too, what would be the next, easy to understand, ways to decipher it?
I found the "Hill climbing" concept, of starting with a random set of replaces, compare results with a dictionary, try some changes and repeat (that seems like a genetic algorithm idea to me). But I would like to learn some other easy ideas.
PS: Looking for questions about it, I read something about "word patterns", but seems not too easy to code.

Edit: I have to add that I tried to find word patters in the book "A pale blue dot" by Carl Sagan. The pattern of the first 202 unique longest words in the book had only 1 match with a word in the dictionary (although I used a 80k words dictionary, so only 70 of that patterns matched a word there, Sagan seems to use infrequent long words).
Only the 203th longest unique word in the book had 2 possible words in my dictionary for its pattern. So, because I'm using a long text like a book, I have plenty of unique long words to create a substitution table, thus the method is easy to code.


texts:
I am updating a system that has Rails' OpenSSL on one side and Python's cryptography.io on the other.

The Rails side has to generate keys for the AES-256-GCM and here are two methods that appear to work:

SecureRandom.hex
# => "3d499a7b8f57773281ca2d47698a0062"

OpenSSL::Cipher::Cipher.new("aes-256-gcm").random_key
# => "\x1A\xAC\x8F\xC4mX\xAE\xDE\x04\xE1\x83\x8F\xFF^\x8C3KJ\xBE\vt\xE4\xBC\x14B\xDEro\xB8\xF5Yy"

Due to the transmission, it is currently easier to use SecureRandom.hex, but I believe that its reduced charset would make it less secure for any given length. Is this a valid concern (meaning I should spend more time making the OpenSSL version work), or is it reasonable to use SecureRandom.hex to generate keys?


texts: Encypted comms between two parties with facilitating middleman

texts:
Charlie knows both Alice and Bob. Alice wants to send a message to Bob. Charlie must at all times know that Alice is sending Bob a message but must never know the content of the message.

The message can go from Alice to Bob direct or via Charlie. But at no time should Charlie know the content of the message.

The solution I can think of is to use Signal protocol with Noise Pipes (like WhatsApp).

Is that approach ok? Is there a simpler approach to the problem?

Thanks


texts: Verifying randomness and uniqueness of TRNG output

texts:
We need to verify two claims about a set of numbers:

They are random
They are unique in the set (the set is about 200 billion (2TB bin storage))

Supposedly, the numbers were generated by a TRNG (based on a radiation detector). The TRNG itself is a PCI Express card (which we do not have yet) and is probably a TRNG feeding a CSPRNG.

What ways are there to verify the claims? For randomness there are the NIST and other specs and tools.

But how can one tie a verification of the first claim to verifying the second (uniqueness in the set)? Keep in mind that the output of the TRNG has almost certainly been filtered from duplicates. That is most probably going to break the randomness tests.


texts: Is Threefish the only cipher with 1024 bits of security?

texts: Threefish has up to a massive 1024 bits of security.  Is it the only cipher with such overkill security?


texts: Are low degree I/O relations in AES possible?

texts: If I restrict the degree of each monomial to say 4 or 5 at maximum. Is it then actually possible to write down the I/O relations for an AES S-box?


texts: Did non-military cryptography appear in the 50's and 60's only due to NSA leaks?

texts:
I'm not talking about scytale, but encryption like RSA, DES, etc.

How exactly did civil cryptography evolve after World War II?


texts:
The flow is like this.

Client sends GET to Server
Server responds with 401 UNAUTHORIZED and the authentication protocol: NTLM
Client re-sends the request including authentication information.

I don't get it. What exactly does the client send at step 3? The password? And if yes, what encoding does it use? The username should be sent in plain text and I don't see it. Here are the HTTP headers:

GET http://example.com
HTTP/1.1 401 Unauthorized. WWW-Authenticate: Negotiate. WWW-Authenticate: NTLM
GET http://example.com Security: Authorization: Negotiate YIIPQwYGKwYBBQUCoIIPNzCCDzOgMDAuBgkqhki...UMVM=

At step 3 I've cut part of text because it was way too long.


texts: Stopping timing attacks on AES: Why is it important to prevent the OS from interrupting the AES computation?

texts:
I read the paper Cache-timing attacks on AES (by Daniel J. Bernstein), but I don't seem to understand everything. The author dedicates a long section on how to prevent the OS to interrupt an AES computation. But how does this leak any information? Yes, the calculation takes more time than usual, but it is not dependent on the input?

(This is a follow-up to AES timing attacks.)


texts: One ciphertext, multiple keys, multiple messages

texts:
I recently came across following idea, does anyone know a name and if it is actually used?

  A wants to send B a message (A and B know both have a common secret
  key) and C wants to intercept it (without the knowledge of the key)

  Now we assume they have an encryption method that let's you define two
  distinct messages for two distinct keys that both are encoded in the
  same cyphertext.

  With this method A can send the secret message "it is raining
  tomorrow" encrypted with the secret key, but A can also include the
  message "it is not raining tomorrow" with another key.

  If C manages to intercept the message and manages to find one or both of the
  keys, they still don't know anything, as there are two contradicting
  messages. But since B knows which key was used, they can use the
  correct message.

If such an method exists, wouldn't it very secure, or are there any problems that come with it? The only problem I can think of is obiously the size of the cyphertext, and depending on the complexity of the messages you might have to find a lot of messages to completely "diffuse" the meaning.

Sorry for the probably not very fitting tags, I did not find any better ones, as this is just a relativel vague question.


texts: What happens if CBC-mode uses the same IV for all processes?

texts: In CBC mode (Cipher Block-chaining mode), each block of plaintext is XOR with the previous ciphertext block before being encrypted. What happens if I use the same IV instead of the previous ciphertext block? Is it vulnerable to Chosen plaintext attack?


texts: When do I need to renew keys for Salsa20 or HMAC?

texts:
I currently have a system which uses two keys sourced from a single key subjected to HKDF. One key is used in the Salsa20 stream cipher and the other is used for a SHA-2 based HMAC.

Given that the stream cipher (Salsa20) is being used for a persistent stream lasting a long time (perhaps hours) with frequent data exchange, is key renewal required (where the key used for the cipher is renegotiated)?

Furthermore, is there a defined period of time in which this key renewal should take place? I read this question here and found that stream ciphers like RC4 and Salsa20 have a period, but is there any security vulnerability in letting their internal counters rollover?

The same questions apply for the SHA-2 HMAC: should the key for the HMAC be replaced after some period of time? Or is the act of replacing the key itself a security vulnerability.

I can provide code if that would be helpful.


texts: RSA-4096 vs AES-256 for secure chat application?

texts:
Which of these two methods suits better the implementation of a secure chat application? In this context, chat will be limited up to 150 letters for one message.
I would prefer RSA because what I know RSA is really secure if it is used for small text and also if I will use groups it is easy in RSA because of public key distribution. Specially for chat application where user can write very small letters message I don't know if AES will be good for security.
AES is better in performance specially if I will compare 256 bit vs 4096 bit. RSA will be slower for encrypt and decrypt. But my goal is to have strong secure chat and not super fast chat.
What would be the more apt method?
I will use this chat only for sending message, e.g. no attachments, etc.


texts: Activation keys and asymmetric encryption

texts:
To me it seems that a quite safe way of creating activation keys is by using asymmetric encryption, so that the end-user could only reverse-engineer the validation method. This way the company keeps the generation algorithm (and key) safe.

Assume one uses RSA encryption with 1024 bit keys. They sign some data with the private key and the result is 128 bytes long.

How can he fit this into an activation key that is much shorter than that? e. g. 16 or 20 chars or so.

The validation algorithm must now decrypt with the public key and see if the message is really coming from the company. How is it done when the full cryptographic message is unknown?

Is there an error in my assumptions above or is it in fact done like this?


texts: why babai rounding technique does not work for finding closest vector using bad basis

texts: Given, a basis of the lattice such that the basis not nearly orthogonal(bad basis) babai rounding technique to find the closest vector does not give the desired result. Can any one explain why?


texts:
I am new to quantum cryptography and I would like to ask about the BB48 protocol. So, understood that the identification of eavesdropping depends on the error rate that is introduced by the adversary. However, I want to know if it is possible for an adversary to eavesdrop on encrypted messages without being detected?
Thank you in advance


texts: Is there a cipher that uses part of the already-computed ciphertext in the encryption scheme?

texts:
Are there any famous ciphers that, to determine the encrypted letter at position n in the ciphertext, it uses the encrypted letter at position n-1 in the ciphertext?

I tried google but I couldn't figure out how to phrase my search terms correctly to find something like this.


texts:
Quantum computation is based on the superposition principle of quantum physics. Bits in a normal computer are either 0 or 1. Quantum physics allows bits to be in a superposition of 0 and 1, in the same way, Schrödinger’s cat can be in a superposition of “alive” and “dead.” [http://nautil.us]

My question is: Can public key cryptography survive quantum computers?


texts: Are there any elliptic curve asymmetric encryption algorithms?

texts: RSA offers the functionality of encrypting (short messages, or symmetric keys) with a public key, and decrypting with a private key.  However, RSA key generation is extremely expensive, especially for 2048-bit+ keys. Is there an algorithm which employs elliptic curve cryptography,  fast asymmetric encryption, fast key generation, and small keys sizes?


texts: Why does the verifier have to send a challenge in Shnorr protocol?

texts:
In the Shnorr protocol where the prover wants to prove he has a witness $w$ for $g^w$ the following interactions happen:

the prover chooses a random $r$, calculates $y=g^r$ and sends $y$
the verifier sends a challenge $x$
the prover calculates $t=xw+r$ and sends it to the verifier
the verifier tests if $g^t=(g^w)^x.y$

My question is why the verifier sends a challenge. Would he be convinced if the prover just sends $t=r+x$ and the verifier tests if $g^t=g^w.y$? Plus $t$ won't reveal the witness.


texts: Generators and Multiplicative group $\mathbb{Z_7}$

texts:
In the multiplication table for $\mathbb{Z^*_7}$, each row has all the elements of the set

My questions are:

  is each element a generator here? if not why?
  is an element considered as generator only if $Order(G) = Order(g)$ i.e $Order(g) = 6$  hence $g=3$ is a generator.
  is there any formula to find the number of generators?
  Some website says phi(n) gives the order of group some says $\varphi(n)$ gives the number of generators some says $\varphi(n)$ gives the number of elements with a multiplicative inverse. Which of these is correct?


texts: Understanding Montgomery's parameterization of elliptic curves

texts:
I'm having a bit of trouble understanding the translation of affine  coordinates to projective coordinates in Montgomery curve ECM. Would be very thankful if someone could explain it by expanding the derivation.

  From: Speeding the Pollard and Elliptic Curve Methods
  of Factorization page: 261.
  $$\begin{equation}\tag{10.3.1.1}By^2 = x^3  + Ax^2 + x\end{equation}$$

  Let $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$ be two points in the
  curve, with $x_1 \neq x_2$ and $x_1x_2 \neq 0$.  Then $P_1 + P_2 = (x_3, y_3)$ satisfies

  $$x_3 = B[(y_1 -  y_2)/(x_1 - x_2)]^2 - A - x_1 - x_2,$$
   $$\begin{align}x_3(x_1 - x_2)^2 & = B(y_1 -  y_2)^2 - (A + x_1 +
 x_2)(x_1 - x_2)^2 \\ & = -2By_1y_2 + x_1x_2(x_1 + x_2 + 2A) + x_1 +
 x_2 \\ & = B(x_2y_1 - x_1y_2)^2/x_1x_2. \end{align}$$

  Similarly, $P_1 - P_2 = (x_4, y_4)$ satisfies $$x_4(x_1 - x_2)^2 =
 B(x_2y_1 + x_1y_2)^2/x_1x_2.$$ Multiply these equations and use
   (10.3.1.1) to obtain $$x_3x_4(x_1 - x_2)^2 = (x_1x_2 - 1)^2$$ after
  division by $(x_1 - x_2)^2$. This equation remains valid if $x_1x_2 = 0$. If $P_1 = P2$, a similar derivation yields

  $$4x_1x_3(x_1^2 + Ax_1 + 1) = (x_1^2 - 1)^2$$  These equations
  reference only the $x_i$, not the $y_i$. Fortunately ECM does not
  require us to compute the $y_i$.

(I  don't understand everything below this point. Could someone help me expand these derivations? Seems like it is oversimplified)

  Let $P$ be an arbitrary point on the curve and let the x-coordinate of
  $nP$ be the rational number $X_n/Z_n$. From the ratio
  $(X_{m-n}:Z_{m-n}),(X_m:Z_m) and (X_n:Z_n)$, one  can compute the
  ratio $(X_{m-n}:Z_{m-n})$ via the addition formula.

  $$X_{m+n} \leftarrow Z_{m-n}(X_mX_n - Z_mZ_n)^2\\ Z_{m+n} \leftarrow X_{m-n}(X_mZ_n - Z_mX_n)^2$$

  if $mP \neq nP$, and  via the duplication  formula $$\begin{align}
X_{2n} & \leftarrow (X_n^2 - Z_n^2)^2, \\
Z_{2n} & \leftarrow 4X_nZ_n(X_n^2 + AX_nZ_n + Z_n^2)
\end{align}$$

  The costs drop if we store the ratios $(X_m:Z_m:X_m+Z_m:X_m-Z_m)$ and rewrite the formulae as (the right sides of the addition formula have
  been multiplied by 4)

  $$\begin{align}
X_{m+n} & \leftarrow Z_{m-n}[(X_m - Z_m)(X_n + Z_n) + (X_m + Z_m)(X_n - Z_n)]^2 \\
Z_{m+n} & \leftarrow X_{m-n}[(X_m - Z_m)(X_n + Z_n) - (X_m + Z_m)(X_n - Z_n)]^2 \\
\end{align}$$
  and

  $$\begin{align}
4X_nZ_n & = (X_n + Z_n)^2 - (X_n - Z_n) \\
X_{2n} &  \leftarrow (X_n + Z_n)^2(X_n - Z_n)^2 \\
Z_{2n} & \leftarrow (4X_nZ_n)((X_n - Z_n)^2 + ((A + 2)/4)(4X_nZ_n))
\end{align}$$


texts: ABC Conjecture's Impact on RSA Encryption

texts: A recent proof of the ABC Conjecture has been released by one Shinichi Mochizuki.  Now, I'm not well versed in mathematics but it would appear that this proof implies that finding prime factors could be greatly reduced in computation time.  Is that right?  Does this show that encryption that relies on prime factors can be cracked quicker?  And if so is it possible that such an algorithm could be produced from these findings to do so either now or in the future?


texts: Noise of ciphertexts in LWE/RLWE based FHE

texts: Often times $[\langle \textbf{c}, \textbf{s} \rangle]_q$ is referred to as the noise associated to the ciphertext $\textbf{c}$, and that decryption is correct when the norm of the noise is $< q/2$. But shouldn't $\langle \textbf{c}, \textbf{s} \rangle$ be the noise instead of $[\langle \textbf{c}, \textbf{s} \rangle]_q$, since $[\langle \textbf{c}, \textbf{s} \rangle]_q$ means the reduction mod $q$ already happened and so the norm of $[\langle \textbf{c}, \textbf{s} \rangle]_q$ is always $< q/2$?


texts: Encryption by repeatedly squaring key and flipping source bits?

texts:
I came up with a simple way to encrypt a series of bits and I cannot seem to find a weakness. I know almost nothing about cryptography so I was wondering if someone could help me out and find the fault in this method. It is incredibly simple, so I'm almost definitely not the first one to try this out, but I couldn't find anything like it online.
Method:
Given are a sufficiently long key and a stream of input bits.

If the last bit of the key is a 1, then flip the current bit in the input stream.

If the last bit of the key is a 0, then don't do anything.

Square the key and truncate it so that it still fits within whatever key size is desired.

Repeat.

This would yield an encrypted stream of output bits.
Executing the same process on an encrypted message would yield the decrypted message.
Thanks in advance.


texts:
How many possible 16 bit S-boxes exist? (AES uses 8 bit substitution boxes)
I first taught of calculating 128(keysize in bits)/8(bits) =16, but I believe it's wrong.


texts: Does Goldwasser-Micali only encrypts only 1-bit or multiple?

texts: I've read online that the Goldwasser-Micali scheme can only encrypt 1-bit then I read that in another pdf that that scheme can encrypt a message of multiple bits so I'm confused. Can anyone clarify please?


texts: Is the member sum of a subset of $\mathbb{Z}/p\mathbb{Z}$ known (with $g^n \bmod p$)? Is it always $\mod P = 0$?

texts:
Let $P$ be a prime and $g$ a value between $2$ and $P$.
Let $M$ be the set of numbers which can be generated with $g$:
$$M = \{g^n\bmod P, \text{ with } 0 < n <P \}$$
If $g$ is a prime root of $P$ all values $1$ to $P-1$ can be generated.
The sum of those would be:
$$S=\sum M = \sum_{n=1}^{P-1} (g^n \bmod P) = \sum_{n=1}^{P-1} n= (P/2)\cdot (P-1)$$

Is there also a formula for values $g$ not a prime root of $P$?
(So for generators $g$ which are only able to generate a subset of   $\mathbb{Z}/p\mathbb{Z}$)
Question: What is exact sum of such a subset?

Partly solution:
During testing around I noticed one factor of this sum $S$ seems to be $P$.
So
$$ S = \sum M = c \cdot P$$
and with this
$$ 0 \equiv S \bmod P$$

Is that always the case? EDIT: seems to be the case, see comment from  runway44 (edit end)
Any way to calculate this factor $c$?

Example: $g=13, P=23$
With $g=13$ only half the numbers out of $\mathbb{Z}/23\mathbb{Z}$ can be generated:
$M = \{13,8,12,18,4,6,9,2,3,16,1\}$
sum $S=\sum M = 92$, which is $4 \cdot P$
Why $4$ times? Any way to compute this factor?


texts:
I need to make it clear I  know nothing about crypto so in that context I'm hoping to clear up some confusion:

As I understand it a "round" in a cipher is one encryption operation and a cipher like AES has multiple rounds. Did I get this right?

I've seen descriptions of attacks against a cipher say something like it "broke 4 out 8 rounds". In this case, if the plaintext wasn't recovered than how is it determined that any number of rounds were broken?

Thanks


texts: A simple client/server authentication protocol

texts:
Some days ago I asked for a help to find and correct the problems of an authentication protocol. I closed the post because I was convinced I can correct it but, unfortunately I'm having some troubles. The "old" post is the following:I'm dealing with this problem: establish if the following protocol is 'secure' and, if it isn't, modify it to make it secure.

I will use the subsequent notation to describe the protocol:

$N$ is a nonce
$X \longrightarrow Y: \space   M$
to indicate that $X$ sends $M$ to $Y$
$K_{XY}$ to indicate the symmetric key shared by $X$ and $Y$
and $K_{XY}(M)$  to indicate that the message $M$ has been encrypted with the symmetric key $K_{XY}$.

The protocol allows a client $C$ to authenticate itself to a server $S$ using an authentication service $A$.

$C \longrightarrow S:\space  C$
$S \longrightarrow C:\space   N$
$C \longrightarrow S:\space   K_{CA}(N)$
$S \longrightarrow A:\space   K_{SA}(C, K_{CA}(N))$
$A \longrightarrow S:\space   K_{SA}(N)$

$S$ authenticates $C$ if and only if the nonce received $N$, got by the authentication service ($A$), is equal to the nonce sent to $C$.

Assuming the communication channel is not secure, an attacker (called Eve) can impersonate $C$ simply sending the message "C" and $K_{CA}(N)$ whenever $C$ tries to authenticate himself.

How to avoid impersonation and offline nonce-guessing in this case? Any suggestion? I don't want the answer to the problem, just a few tips to continue on my own. At the end, I want to say that I know how to make the protocol secure but my answer consists in completely change the protocol described above, and so I think my answer is not the most appropriate. Recently I thought to modify the protocol as follows:
$C \longrightarrow S:\space  C$
$S \longrightarrow C:\space   K_{SA}(N)$
$C \longrightarrow S:\space   K_{CA}(K_{SA}(N))$
$S \longrightarrow A:\space   K_{SA}(C, K_{CA}(K_{SA}(N)))$
$A \longrightarrow S:\space   K_{SA}(N)$ Can it work now?


texts: What do the magic numbers 0x5c and 0x36 in the opad/ipad calc in HMAC do?

texts:
Wikipedia lists the following pseudocode for HMAC:

function hmac (key, message)
    if (length(key) > blocksize) then
        key = hash(key) // keys longer than blocksize are shortened
    end if
    if (length(key) < blocksize) then
        // keys shorter than blocksize are zero-padded ('∥' is concatenation)
        key = key ∥ [0x00 * (blocksize - length(key))]
    end if

    // Where blocksize is that of the underlying hash function
    o_key_pad = [0x5c * blocksize] ⊕ key
    // Where ⊕ is exclusive or (XOR)
    i_key_pad = [0x36 * blocksize] ⊕ key

    // Where '∥' is concatenation
    return hash(o_key_pad ∥ hash(i_key_pad ∥ message))
end function

Why are they there?  How were they chosen?

It seems to me that  $hash(key + hash(message))$ (where + is concatenation) would suffice.

Obviously I'm missing something.  What is it?


texts: Which tamper-protection algorithm provides the shortest output?

texts:
Background

When making web applications you sometimes need to pass data along with the form which isn't visible to the user. Database IDs are the most common, but texts and IDs are sometimes necessary too. For this reason there is a <hidden> field in HTML, but it has a drawback - any hacker with a basic understanding of what he is doing can modify the value. It would be better if such values would be tamper-protected, if not outright encrypted.

Question

I need to pass a value through hostile territory. The value is most often an integer (and that most often less than 65'000, so mostly just two non-zero bytes, rarely three, almost never 4). However sometimes the value can also be a string (short, a few hundred characters at most). I'm OK with using different algorithms for different kinds of data.

I want to tamper-protect the value, so that it cannot be changed en-route without detecting. Hiding the data isn't necessary, but doing so would be a bonus. So either tamper-protection or encryption would work.

Whatever the algorithm, I want to have the output as short as possible without sacrificing too much of security. This is because it's a webpage and shorter data means faster response times. Also, the HTML code becomes easier to read if there aren't lengthy random strings in it.

What algorithms would you suggest for this purpose?


texts: In a specific Paillier implementation, why is r prime?

texts:
I have a question about an implementation of the Paillier cryptosystem.

In the description of Paillier above, encryption of a plaintext message $m$ on $\mathbb {Z}_{n^{2}}$,  $0\leq m<n$, proceeds by choosing a random number $r$ such that  $0 < r < n$ and computing the ciphertext as $c=g^{m}\cdot r^{n}{\bmod n}^{2}$ for generator $g$.

However, in one open source Paillier implementation in Python, the encryption function creates $r$ as a prime number, making for slow encryptions.

I am curious about why $r$ is made prime in that implementation, when no such restriction exists in the public algorithm description.   Could it be that it is a mathematical shortcut, or a compensation for some other shortcut, perhaps as the generator g is "hard coded" to $n+1$, rather than chosen by random/trial testing?

Is there any risk in changing the implementation to make $r$ random but not necessarily prime?

I mean no discredit to the author of the code.  It is robust code and has served me quite well.  I want to understand the reasons why the restriction.  Thanks!


texts:
I understand modular arithmetic(or at least I think I do!) and I've tried to read and learn about how the Math in RSA works(and I think it went pretty well). I've been reading up on ECC and it looks very interesting and I tried solving a few basic math problems that involve ECC. I understand the basics, now I'm trying to understand it on a deeper level.

I find it easier to learn where I have analogies so my understanding stands as follows at this point — ECC is not a cryptosystem as such, it is a technique, much similar to the concept of using primes in RSA. Using ECC, encryption algorithms such as El-Gamal and signing algorithms such as ECDSA can be implemented.

I understand the properties about what a group, field are : However I see this statement in quite a few places. My doubts are as follows:

What does it mean to say “E is an elliptic curve over $\mathbb{F}_p$, where $p$ is prime"?
Does the cardinality of a curve mean the number of primes that are on a curve?
How does real-world ECC encryption work? In a problem I had tried solving, the message was denoted as a point on the curve. However, I imagine that its infeasible/impractical to always be able to denote messages as a point on the curve.
Any additional reading resource suggestions would be awesome!