Can perfect forward secrecy introduce vulnerabilities? Is it always a win or could PFS algorithms introduce new attack vectors or weaken the level of secrecy vs not being used?

Yes, PFS could introduce new attack vectors.

PFS makes it hard to impossible to find / reconstruct a private key used for previous / future connections. It is not some special sauce that makes an algorithm invulnerable to attack.

Any change can always introduce vulnerabilities on an implementation level, as SEJPM already stipulated. This is also true on the protocol level, for instance it is possible to forget to authenticate the parameters, allowing for MitM attacks.

As for the algorithms used: well, it simply depends on the algorithms themselves. For ECDHE: you could forget to validate that a public point is on a curve for ECDHE. You must make sure that the security requirements for particular algorithms are met.

More broadly ECDHE is more vulnerable to attacks using quantum computers than RSA. So if quantum computers ever mature then a specific PFS algorithm could fall earlier than a previously used algorithm. However, you could also use finite field DHE for PFS and ECIES for "normal" key establishment, which would give the advantage to the PFS algorithm.

One pitfall is that servers may be more inclined to use smaller key sizes. Whereas a key in a RSA certificate is likely required to have a particular key size (by the Certificate Authority that needs to sign the certificate), nothing prevents a server to choose the smallest key size available for a protocol. For a long time DH implementations maximized the key size to 1024 bits, a key size that would be considered well below the minimum by now.

It might also be that the random number generator on the server could be bad. When using RSA encryption the pre-master secret is generated by the client. It could be that the server has a bad RNG and leaks information about the RNG state through the generated key pair. It may also use more random values and deplete the RNG of entropy. This again is more an implementation issue but it also shows that additional requirements may have to be met to support PFS algorithms.

Note that you asked for ways how PFS could weaken security. In general the advantages of PFS are very likely to outweigh the disadvantages. But if you ask a security professional to search for vulnerabilities you are likely to get a long list of possibilities, some more likely than others...


How to determine which type of transposition cipher I have? I have some ciphertext that I have determined using frequency analysis to be most likely encrypted using a transposition cipher, as the letter frequencies are similar to plain English language text. I believe the next step should be to determine which transposition cipher it is, but I don't know how to do that.
Am I right to assume that what I have is definitely a transposition cipher? And if so, how do I determine which transposition cipher it is?
For what it's worth, here is the ciphertext I have. But (as asking for decryption of a specific ciphertext would be off-topic here) I'm interested in general techniques that could be applied to any ciphertext.
CTCRAL TYNIH ORFLN NLONH LTOWH SLINI IIEER NOENT AHRNE NWAAM CTEAK ERDHH
DMIOD AEINA YTFEI IEINM FSTGI UOVED GLMEI YINEE EYNGS BSCRA TUVGU UEIEV
OHIDA TISRO IEEEA TETMG RSFHD DHARA ICSEU EVHNS WIYII YIRND TFVCX GSMVL
IUELH RETRG NNREC ONEYI OTLUN SBRSH AIIEE TTOOI ESCLS KWSLE ETGHN EOTNU
STGIM EEACR TAEEN LAPEH RHNHE GWIEH EWRNN UETHT EPREN SDNFW YUFGI TUEAY
ETLMR TBIPW UPANI OEFUS RSEAT NRTDP RENOA EETIL HNNAD HECWD TTILI UECDT
DTLAM RQERS MVVTR HYTYO UFOAM ONCNS NFSST EEVHA YHERE OEONM RE- GAO HCVLO
COIYT HSENZ FAHHL LYRII USBAS IEHEO IOSOT TILAI EOGOT ETEHL DEENP AEISP
IDDMT RHNBI EEEMO NTIOE ISGZE SEAEE IDLNI TRTTD RIDUT PTNIY NIYNQ MMMIR
BDAOI AYDOT DTELG HAIHO BDESA RSYLN HNWCN TRLRE NTAMN AESEI EHAEY NHGMO
REFOT TFTUP AEREE HTONG OISHT TVEHO MSEFO OLINE TOLET SOATR AERTC TGEGT
STTNA ONNTG OHAIA TYUOT IIARN TENCO TKGAU TSEHH EIBWO SDTUW INDTR UECHC
RSEAT DEOEW ENWFA ELGKM

However how do I determine which transposition cipher I would need to use? Am I right to assume this is definitely a transposition cipher also?

As you found out that the ciphertext has a similar frequency to the English letter frequency. This can lead to lots of possibilities

It can be a shift cipher, that is the generalization of the Caesar cipher $$c = m + k \bmod 26.$$ In the Caesar cipher, the $k=3$ is fixed. There are at most 26 candidates to test, not so far.

It can be a permutation cipher, that is there is a permutation $\pi$ on the alphabet that permutes the letters. The 1000 years old frequency attack work on this. You need to swap the top three letters and try to reveal some other. Since you have a long message this should be working very well. Actually, the substitution cipher is also a permutation cipher.

It can be any of the transposition ciphers since they are keeping the letter frequency, too.

Rail fence cipher
Try some possible rail lengths. It is a very weak cipher. The below is the Rail Fence histogram with rail size 3. This is exactly the same as Moby Dick's frequency since the letters are not permuted, just the positions changed. The same applies other transposition ciphers since they just transpose.

Scytale
The cylinder size cannot be too long. try some possible sizes.

Route cipher
Row size and route to read the letters are required. Don't expect the road to be too complex. Set a row size and test for well-known routes. spiral inwards.outwards, clockwise/anticlockwise, starting from the top right/top left, bottom right/ bottom left, etc.

Columnar transposition

 Guess the column size and look for digrams to determines the permutation on the columns.

Double transposition
This is hard to attack, it takes the result of the column transposition and applies another transposition. Still, we have computers, and once can test all values up to some limit and check for the string in the decrypted text. Linux's strings command can be helpful to distinguish those.

Myszkowski transposition
Just a modification of the Columnar transposition that deals with the reoccurrence of a letter in the key. Increases the key space a little bit.

Disrupted transposition

Grilles
This is one of the hardest ones in this series since the attacker needs to form the grille. Gaines book's chapter is advised. It has some variants.

We don't expect combinations since the combinations can hide the frequency.

Vigenère cipher
It is not expected to be Vigenère cipher, however, the Kasiski test can be used to test.

Online Tools

Crypto Tools 2
dCode.xyz
boxentriq

I also did;

The light gray is from the Moby Dick text, the medium grey is your text.
In a bar, a light grey on the top means that moby dick has a higher frequency, a medium grey on the top means that your text higher frequency, a sample Python code, and Moby Dick is here.
From here we can simply say that it cannot be Caesar or Shift Cipher since the frequency is very close to the real English frequency!.


Why does verifiable secret sharing with an honest majority require a broadcast channel? In the information-theoretic model with active adversaries, it seems to be well-known that no protocols with exact reconstruction of the secret exist for the task of verifiable secret sharing (VSS) when $t \geq n/3$. However, one can lift the number of tolerable cheaters by allowing for a small error probability during reconstruction to up to $t < n/2$ cheaters. For such protocols, broadcast channels are assumed to be available (in addition to secure, authenticated communication channels) and it seems to be a well-known result that without this assumption, even this weaker form of VSS is impossible (see e.g. the abstract of the paper linked below).
My question is, why is the assumption of a broadcast channel necessary? To me it seems that a possible reasoning might be that (1) broadcast channel is equivalent to Byzantine agreement, (2) Byzantine agreement is impossible for $n/3 \leq t$ and (3) VSS implies a broadcast channel, hence broadcast needs to be assumed for VSS when $n/3 \leq t < n/2$.
https://web.cs.ucla.edu/~rafail/PUBLIC/145.pdf

By definition, VSS implies broadcast. As such, with $t\geq n/3$, it is not possible to achieve VSS (by the bounds on Byzantine Agreement).


Fast AES-128 on 32 bits encryption Suppose in AES-128, there are $5$ tables, namely Te0, Te1, Te2, Te3, Te0 which help in fast encryption on $32$ bits CPU. Each table contains 256 numbers, where each number is $4$ bytes.

Te4's numbers are generated by repeating hexadecimal in S-box. So Te4 contains numbers $0x63636363U, 0x7c7c7c7cU, 0x77777777U, ...$.

Te0 contains numbers which is obtained through the degree-wise multiplication between $\{ab\} x^3+\{ab\} x^2+\{ab\}x+\{ab\}$ and $\{02\} x^3+\{01\} x^2+\{01\}x+\{03\}$. The first polynomial is the number in Te4. So the first number in Te0 is $0xc66363a5U$, which is obtained through $\{63\} x^3+\{63\} x^2+\{63\}x+\{63\}$ and $\{02\} x^3+\{01\} x^2+\{01\}x+\{03\}$.

Te1's numbers are obtained through $1$ byte right rotation on numbers in Te0. So Te1 contains $0xa5c66363U$. Te2 and Te3 are also obtained by $1$ byte right rotation.

The followings are the screenshot of the five tables:

Question: If only table Te0 is used in the program, explain how to perform encryption.

I think we have to perform computation on the numbers, but I don't know how to do it. Would appreciate if anyone can give some hints on it.

There's no particular computation you have to do.

Since all other tables could be computed just by rotations of Te0 what you need is just to perform rotations, xors and table lookups.

Here's what usually done when you have only Te0.

You read the state column-wise, keeping in one 32 bit variable/register the value of one column. (As convention hereafter, the most significant byte of the 32 bit variable encodes the top byte of the column in the 4x4 AES state matrix).

Now what you want to perform are ShiftRows, SubBytes and MixColumns is:

uint32_t a[4]; //This contains the state
uint32_t b[4]; //This will contain the state after ShiftRows
                         //SuuBytes and MixColumns

b[0] = Te0[FIRST_BYTE(a[0])]  ^
       rotateL8 (Te0[SECOND_BYTE(a[1])]) ^
       rotateL16(Te0[THIRD_BYTE (a[2])]) ^
       rotateL24(Te0[FOURTH_BYTE(a[3])]);

Where the X_BYTE are macros returning the X most significant byte of the uint32_t, and the rotateLX macros perform left rotations of X bits.

The explanation is as follows:
As input it is taking first byte of first column, second byte of second columns, etc.
This is made to perform ShiftRows. In fact, the input will be the first column after ShiftRows operation.
The table lookups by Te0 will return a word, containg: 2*Sbox(input), Sbox(input), Sbox(input), 3*Sbox(input)

Note that this corresponds to the first column of the formulas below, which is used to calculate MixColumns as shown in the wikipedia MixColumns page

$b_0 = 2a_0 + 3a_1 + 1a_2 + 1a_3$

$b_1 = 1a_0 + 2a_1 + 3a_2 + 1a_3$

$b_2 = 1a_0 + 1a_1 + 2a_2 + 3a_3$

$b_3 = 3a_0 + 1a_1 + 1a_2 + 2a_3$

Note that the addition in the above formulas are additions in $GF(2^8)$ and corresponds to the xors used in the C code.

Therefore when you do the second table lookup you need to rotate the result left by one byte, in order to match the second column in the formula above, and so on for third and fourth table lookups.

To evaluate a full round you need to evaluate the other 3 columns, the code is the same, you just need to rotate the indexes of a. So a full rounds can be obtained by:

for (int32_t i=0; i < 4; i++)
{
   b[i] = Te0[FIRST_BYTE(a[i])]  ^
          rotateL8 (Te0[SECOND_BYTE(a[(i+1) % 4])]) ^
          rotateL16(Te0[THIRD_BYTE (a[(i+2) % 4])]) ^
          rotateL24(Te0[FOURTH_BYTE(a[(i+3) % 4])]) ^ round_key[i];
}

Where the addition of $round_key[i]$ performs the AddRoundKey operation.

Please note that the final round requires special treatment since no MixColumns is performed. You will need to do the table lookup and just keep the second or third bytes (which corresponds to the Sbox of the input) discarding the rest. Something like:

for (int32_t i=0; i < 4; i++)
{
    b[i] = (SECOND_BYTE(Te0(FIST_BYTE(a[1]))) << 24) ^
           (SECOND_BYTE(Te0(SECOND_BYTE(a[(i+1) % 4]))) << 16) ^
           (SECOND_BYTE(Te0(THIRD_BYTE (a[(i+2) % 4]))) << 8 ) ^
           (SECOND_BYTE(Te0(FOURTH_BYTE(a[(i+3) % 4]))) ^ round_key[i];
}


ECKS-PS algorithm: searching in encrypted data; bilinear maps I have found an encryption algorithm named ECKS-PS (published in the paper Efficient conjunctive keyword search on encrypted data storage system) that allows an user to search in encrypted data. All the steps are described here:

And I have written them a little bit more clear here:

I have tried to find a calculation example of finding two words multiple times:

but I never get a match.

Can anybody tell me what I am doing wrong and/or provide me with an example where you get a match (based on the ECKS-PS algorithm)? I know there may be other algorithms to search in encrypted data but I would like to know how to do it with this algorithm.

EDIT: with some advice from Barack and Gilles

$e(i,j) = 53 ^ {i*j} \mod 59 $

$ g=53 $,
$ \alpha = 7 $,
$ r= 16 $,
$ \theta = 3 $,
$ a_i = 6 $,
$ Hash(W_1) = 53 ^ {23} $,
$ Hash(W_2) = 53 ^ {18} $,

$e(g^{a_i \theta}, g ^r  ) = 53 ^ { 53 ^ {6*3} * 53 ^{16}} \mod 59 = 53 ^ { 53 ^{34}} = 9 $

$e(g^{a_i }, (Hash(W_1) * Hash(W_2))^{\alpha} * g^{\theta * r}  ) = 53^ {{({53 ^ {23} * {53 ^ {18} }}) ^ {7} * 53 ^{16*3} }} \mod 59 = 9 $

$e(g^{\alpha}, Hash(W_1)^{a_i}) = 53 ^ {{53^7}*{{53^{23}}^6}} \mod 59 = 19$
$e(g^{\alpha}, Hash(W_2)^{a_i}) = 53 ^ {{53^7}*{{53^{18}}^6}} \mod 59 = 27$

$\frac 9{19*7} => $ multiplicative inverse of $ 19*27 \mod 59 = 36$ => $29 \mod 59  \ne 9 \mod 59$


Hash and (MAC) based signatures using zk-SNARK I was wondering if we could use any general symmetric key MAC, a collision resistant hash $H$ and zk-SNARK (or any general NIZK scheme) to construct a signature scheme. I have a MAC key $k$, which is also my private key, and the public key is $h = H(k)$. As a signature for the message is $(mac = MAC_k(m),\pi)$  where $\pi$ refers to a proof using SNARK circuit which takes public input $m,h,mac$ and private input (witness) $k$ and calculates $mac' = MAC_k (m), h' =H(k)$ and outputs $1$ iff $mac=mac'$ and $h'=h$ .
Looks like we need to be extra careful if the MAC above is an HMAC with the same hash function $H$ since it uses actual $Key' = H(Key)$ if the $Key$ longer than block size,other than that are there other issues with it?
Is it secure?
If it is not secure can anyone give a reason why? Way to recover key or forge a signature would be even better.

This is a valid paradigm for building a signature scheme, although a secure commitment scheme should be used to commit to $k$ instead of just using $H(k)$ as the public key. This type of construction was published by Bellare and Goldwasser at CRYPTO'89; see New Paradigms for Digital Signatures and Message Authentication Based on Non-Interactive Zero Knowledge Proofs. Formally, they use a NIZK, as you stated.


How does forking lemma work in regard to Digital signatures produced by GPV hash and sign algorithm based on lattices? I am working on understanding the concepts and approach behind digital signatures that are based on lattices specifically the GPV algorithm.

During the security reduction of this method, the forking lemma is used to show that the attacker can generate a correct forged message.

I read about the forking lemme and I am not able to understand it completely and its application here. This is mainly because I am not predominantly from a math background.

I am looking for a simple explanation of how forking lemma works to forge a signature in this scheme.

While, as Chris said, GPV does not rely on the forking lemma, here is a cute metaphore for it.

Imagine a video game, with n level. The game is tough, and at each level, you have a probability 1/2 to die. If you die you have to restart from scratch. It's running on a very old game console, and you can not save your game. So, you'll need an average of $2^n$ trials before you win the whole game.

The game remains fully deterministic though, and the only source of randomness is your limited skill to reproduce exactly the same sequence of keystrokes on your gamepad.

The forking lemma can been thought as a small device in between your gamepad and the console, that can record your keystroke and replay them. So, if you were lucky enough to succeed level 1, but fail level 2, you can replay exactly the winning sequence of keystrokes for level 1, and therefore directly replay level 2, to try a sequence of keystroke there. With such a strategy, you can win the game playing on average $2n$ levels.

Back to the crypto-world, the deterministic console is the attacker, and the  sequence of keystrokes of each level are the responses of the random oracle to each hash queries. Using the forking lemma strategy, you can try several response for a given request, without having to rerandomize all the previous responses. This way, you can somehow trick your attacker to get to a particular situation much more efficiently than hoping a random set of $n$ response will get him there.


Computing the powers of hash (ripemd-160) function Is there a way I can compute $2^{100}$th power of ripemd-160 of my string, just like I can do with square matrix powers? I.e. can I easily compute ripemd-160 large amount of times?

The only way to do so with cryptographically secure hashes is to perform the actual computations... (i.e. this is not a feature any hash propose to the extent of my knowledge, nor will likely propose in the future.)

But this is not practically possible since if you were to perform such a feat, then you'd be able to perform a brute force collision search attack on a 200-bit hash... Since Ripemd-160 is only 160 bits, the complexity of such a brute force attack is only $2^{80}$ (without any optimization). This means that you would exceed the computing power needed for it.

For reference, SHA-1 was broken after a whooping $2^{63}$ operations, and it took the equivalent of 6,500 years of single-CPU computations or 110 years of single-GPU computations.


Can one implement AES on 4-bit microcontroller? It is possible to implement AES on 4-bit microcontroller? As far as I know, AES on 8-bit microcontroller are common especially for light weight application such as the RFID.

I have yet to come across AES been employed on 4-bit microcontroller, therefore I have been wondering whether such implementation is feasible.

Yes, AES could be implemented on a 4-bit micro-controller such as this EM6626, and that would not be rocket science or stupidly slow. This application note illustrates that all kind of 8-bit operations are simple, and table lookups are possible.

In fact, tables are not even indispensable if performance is non-critical; see this minimalist AES source code in C which has a compilation option to avoid any table.

The most serious issue is the amount of RAM required: current 128-bit subkey and 128-bit data will eat half of the total 512-bit RAM of the above device.

Also worrying is the security: I know no 4-bit micro-controller with any kind of security evaluation. Thus I would trust such an implementation only if it is operated in a secure environment, and with a key that vanishes from the device after use. That's an appropriate security model for an enciphering machine, but not a copy-protection dongle.


Factorize RSA knowing several N and E I did a CRT challenge yesterday and there`s one problem I was unable to solve, probably due to my lack of understanding advanced crypto math.

It`s about RSA. There are ten given pairs of N and E (modulo and exponent). E is always the standard exponent 10001 (hex). N is a 2048 bit number.

The task: factorize all N.

Well, I tried everything known to me (CRT, Wiener, p-1), no luck. Now it occurred to me that maybe 10 pairs aren't given to keep you busy but that maybe the vulnerability is located there?

Any ideas?

no, I don't have the data anymore. :)

If the moduli share no commonness / weak properties, it's impossible to solve the problem as given at hand. (As CodesInChaos pointed out)

Now as you're given RSA moduli, which are always constructed as $n=pq$, you can be sure that if you find $gcd(n_1,n_2)=R>1$, than either $R=p$ or $R=q$ must hold.
As you pointed out in the comments you indeed found such an $R_1$ for $n_1,n_2$. Now you reconstruct $P_1=n/R_1$ and check if $P_1*R_1=n$ holds, which is the case.
In the next step you check wether $P_1$ or $R_1$ divide any of the other moduli.
If it does, you reconstruct the other prime of these moduli via $n/R_1$. You repeat this procedure for all factors you're given.
As soon as you've done this step and still have unfactored moduli left, you try to apply the GCD on all pairs of unfactored moduli and use the resulting factors to obtain the remaing factors and factor the remaining moduli.


What are the differences between a UHF (as used in cryptography) and a cryptographic hash function? After reading about UHFs from different sources (From Algorithm books to Crypto books), I am still thoroughly confused about them.
How is a UHF different from other cryptographically secure hashing functions? Is the only difference that it's a keyed hash function while other secure hash functions need not be keyed?
Also, Boneh defines a UHF as a keyed hash function which satisfies a very weak notion of collision resistance and he goes ahead he defines this notion by saying that the adversary must not be able to find a collision with no information about the key at all. Other than the mention of the key - this seems similar to the adversary having to find a collision where he can pick both m1 & m2 such that there is a collision. If the user can pick both messages to find a collision, then Christof Paar defines that as strong collision resistance rather than weak collision resistance. Paar's definition of weak CR is that user is given m1 & it's tag & he must find a m2 with a collision.
So I am confused here about a couple of things

Is UHF just a cryptographically secure hash function which is keyed?

What Collision Resistance property does a UHF need to possess - Weak or Strong CR & how do you define that type of CR?

The usual definition for a hash function - to avoid hard coded collisions, i.e. trivial formal adversaries have a collision as part of their description and just output it- is as a pair of algorithms $(\operatorname{Gen},\operatorname{Hash})$. In this definition $\operatorname{Gen}$ typically picks a "key" for the hash function, which for the "keyless" ones can usually be seen as the details of the description, like the exact structure and constants.
The advantage of an adversary $\mathcal A$ against the collision resistance of a scheme $H$ is then defined using the following experiment:

$k\gets \operatorname{Gen}(1^\kappa)$
$(m,m')\gets\mathcal A(1^\kappa,k)$
$\mathbf{Adv}_H^{\text{CR}}(\mathcal A;\kappa)=\Pr[\operatorname{Hash}(k,m)=\operatorname{Hash}(k,m')\land m\neq m']$

A scheme is then called collision-resistant if for all polynomial-time adversaries $\mathcal A$ the advantage $\mathbf{Adv}_H^{\text{CR}}(\mathcal A;\kappa)$ is negligible in $\kappa$.
This definition essentially amounts to "give the adversary a full description of the scheme and then they win if they find a collision". The key serving the role of the definition of the hash function having only existed for so long in the real world, i.e. the key being given to the adversary the moment the hash function design was finalized.
Now for a UHF on the other hand the security definition is much weaker. The advantage of an adversary $\mathcal A$ against the universal hashing security of a scheme $H$ is then defined using the following experiment:

$(m,m')\gets\mathcal A(1^\kappa)$
$k\gets \operatorname{Gen}(1^\kappa)$
$\mathbf{Adv}_H^{\text{UHF}}(\mathcal A;\kappa)=\Pr[\operatorname{Hash}(k,m)=\operatorname{Hash}(k,m')\land m\neq m']$

A scheme is then called universal hashing secure if for all polynomial-time adversaries $\mathcal A$ the advantage $\mathbf{Adv}_H^{\text{UHF}}(\mathcal A;\kappa)$ is negligible in $\kappa$.
As you can see for the UHF security, the adversary doesn't get a full description of the scheme. They don't even get oracle access - i.e. they can't query values to get their hashes. So they have to come up with a collision that works for a non-negligible amount of instantiations ("keys") of $H$. Obviously this definition is much easier to satisfy. In cryptographic practice dedicated UHF schemes actually even break down in security if an adversary learns a single input-output pair, allowing an adversary to completely recover the key $k$ and produce collisions at will.


Whats the point of an IV if public? What is the point of the initialization vector in cryptographic modes like AES-CBC when it is sent in the public?
Cant any attacker just listen and reverse the IV? and as such defeating its purpose?
EDIT
I already know what has been said here. My question was: Can't any attacker just listen and reverse the IV? And as such defeating its purpose?
So, by using IV, the message 'hello' becomes (XXXX) and (yyyy), but since both have a copy of their respective IVs in the public such that (XXXX)123 and (yyyy)456, why can't I use 456 to make (yyyy) back to (XXXX) (to clarify)? I am assuming that the decrypter of (yyyy)456 transforms the message in the following ways (yyyy)456 -> f(456) -> (XXXX) -> f(key) -> 'hello'. So why an attacker can't just (yyyy)456 -> f(456) -> (XXXX) if 456 is already known?

Encryption schemes that use IVs will typically use results from previous block (or some counter combined with IV) to generate a pseudo-random bit stream to encrypt or decrypt the next block.

Without an IV, the pseudo-randomness can be based only on the key and the message (because that is the only data that the sender and receiver will both have). Which means it would be relatively easy to get repeated blocks across similar messages using the same encryption key, especially at the start of the encryption. Depending on the mode of operation, it might result in repeated blocks elsewhere too.

In addition, the IV in systems that use it is not combined in a reversible way isolated from the key. E.g. it is not simply XOR-ed into the encrypted text, or fed into the algorithm in a way that is reversible (except if you know the key it is reversible). Instead it is fed into the encryption algorithm as a modifier to the first bock of plaintext in CBC mode (when its influence changes seed generation in all consequent blocks), and/or in other modes as a modifier to the seed to the PRNG creating the bit-stream for encrypt/decrypt. To construct the full seed (and thus successfully decrypt) you need to know the key and IV at the same time - knowing just the IV would not be enough to reverse its influence. In your comment you suggest that the effect of an IV could be removed from an encrypted string, thus rendering it ineffective - because you would then have essentially the encrypted message without any influence from the IV. However, this is not possible with schemes that correctly use an IV - to perform this reversal, you would need to already know the key.

The purpose is therefore to allow re-use of same key, without any chance of exposing similarities in blocks of encrypted data. If all your messages started 'Dear Fred', then without an IV block (or some equivalent additional data to feed the PRNG given the same key), the similarity would show if you used the same key, and this would give away some information about the content of your messages.

As such, it doesn't matter that the IV is public, just that it is unique amongst all messages using the same key. The IV for encrypted messages is serving a similar purpose as a salt used for secure hashing.


However, when I tried using an online AES encyption tool encrypting a 16-byte message produced 32-byte output. How is that possible? What am I not understanding correctly?

The tool in question seems poorly documented for implementation validation. It appears that it performs padding to deal with arbitrary length inputs. This padding is necessary if you want to encrypt arbitrary length messages in a reversible way, however, this implies that you need to add at least one message to the plaintext before encrypting it. This expansion yields the observation: A 16-byte message needs padding to ensure padding is there to be removed. However in a 16-byte block, there's no space for extra padding, so a second block is produced and appended only containing padding.
If you insist on using this tool, it should be possible to do so but just taking the first 16 bytes of the output as the plain input.
Alternatively, you can use tools that don't perform unspecified padding or use the test vectors specified in FIPS-197 (PDF).


Can an RSA encrypted message be altered? Let´s suppose that I want to send an RSA encrypted message to Alice, so I use her public key. Such a message contains a number only. If Eve intercepts the message, is it possible for Eve to alter the encrypted message (the number) so that, when Alice decrypts it she gets twice the original number?

I can think of the following approach but it seems to me an innocent one.
Eve can intercept the message using sniffer software and watch the binary representation of the encrypted number. Eve can then right-shift this binary number (multipy by 2), replace it and route it to the final destination.

I will very much appreciate any comments.

Close; what would work would be if Eve encrypts 2 with the public key (forming $2^e \bmod N$), and then multiplies the ciphertext ($P^e \bmod N$ with that.  When Alice decrypts it (by raising it to the power of $d$, she'll compute:

$$(2^e \times P^e)^d = 2 \times P$$

which is what Eve wants.

On the other hand, this is assuming that Alice uses raw RSA, without padding.  When you add in padding (which any sane use of RSA encryption should use), this doesn't work.


Distortion of the spherical gaussian error through the canonical embedding in Ring - LWE In the paper, "On Error Distributions in Ring-based LWE" by Castryck, Iliashenko and Vercauteren, page 3, It is shown that the distrotion to the spherical gaussian in Ring - LWE is caused by the inverse of the vandermonde matrix and the matrix of multiplication by f'(x). It is explicitly stated that the inverse of Vandermonde matrix B is converted into a real matrix by a "easy unitary transformation". Can anyone help me out in figuring how get such a unitary transformation that takes a complex matrix to a real one?

The section you quote is from the introduction. The paper goes into more technical detail later. For example, equation 3.1 states (roughly) the same equation, and then states that:
$$B = U\Sigma$$
Where $\Sigma$ is the matrix of the canonical embedding, expressed relative to the basis $\{\alpha_1,\dots, \alpha_n\}$, and $U$ is the matrix (defined on page 5):
$$
U = \begin{pmatrix}
I_{s\times s} & 0 & 0 \\
0 & \frac{1}{\sqrt 2}I_{t\times t} & \frac{i}{\sqrt 2}I_{t\times t}\\
0 & \frac{1}{\sqrt 2}I_{t\times t} & \frac{-i}{\sqrt 2}I_{t\times t}
\end{pmatrix}
$$
$U$ is unitary, and known to be an isomorphism $(H, \langle\cdot, \cdot\rangle_H)\cong (\mathbb{R}^n, \langle\cdot, \cdot\rangle)$, where $\langle x,y\cdot\rangle_H = \sum_i x_i\overline{y_i}$ is the Hermitian inner product, and $H$ is a certain conjugation-invariant subspace of $\mathbb{C}^n$ that contains the image of the canonical embedding.
This is all discussed on page 5.


How do I create a cryptographic signature and commitment scheme with accountable evidence? This is a weird one... I am looking for a method which I don't even know how to call, nor whether it actually exists!

Given a pair of asymmetric keys $s_{k}/P_{k}$ and defining $Sig_{k} \dagger B_{i}$ as the signature of block $B_{i}$ using $s_{k}$. Is there a a function $\otimes$ with the following characteristics?

$Sig_{k} \dagger B_{1} \otimes X_{1} => D_{k}$
$Sig_{k} \dagger B_{2} \otimes X_{2} => D_{k}$
$Sig_{w} \dagger B_{i} \otimes X_{i} \neq> D_{k}$

, where $\dagger$ has precedence over $\otimes$.

If I sign a block with $s_{k}$ there should be a bitset $X_{1}$ related with the block $B_{1}$ and, when applying $\otimes$ gives a
$D_{k}$ that has a relation with $P_{k}$.
If any other $B_{2}$ is used there should be a $X_{2}$ that gives the same result.
If a different key pair is used $s_{w}/P_{w}$, we should not be able to find any pair ($B_{i}$, $X_{i}$) capable of resulting in $D_{k}$.

Finding $X_{i}$ from $B_{i}$ or $Sig_{k} \dagger B_{i}$ (to verify the condition) should be easy only if one has $s_{k}$.

We should not be able to infer $P_{k}$ from $D_{k}$ without having the inputs.

Application:

$D_{k}$ serves as a commitment scheme and has the requirement of being immutable for a $s_{k}$.

One can publish a proof of ownership of $D_{k}$ knowing $s_{k}$. This proof has a specific ($B_{i}$, $X_{i}$) pair that is delivered to a specific entity $I_{i}$ (also with the signature). In case that entity publishes the proof without authorization, it can be identified and accountable for the security breach.

The alternative I'm using now is to apply a deterministic signature function $H(Sig_{k} \dagger B) => D_{k}$. Where $H$ is a SHA-256 function and $B$ is static, always resulting in the same $D_{k}$. One cannot infer $P_{k}$ because the signature is hidden using the hash (assuming all $P_{k}$ are public). If I disclose $Sig_{k} \dagger B$ I can prove $D_{k}$ is mine. However, if I share this proof with multiple parties, I cannot use it to "point fingers" in an eventual security breach.

I, personally, did not know of any scheme with such properties yet so I took the challenge of creating one and succeeded. After that, I was really unsure on whether to post it or not since it SHOULD NOT BE USED. I decided to do so for the mere point of showing that such schemes are probably possible.

Given an elliptic curve with a generator $G$ of order $q$ and a hash function $H_q(x)$ which maps $x$ to $[1, q]$:

$\operatorname{GenKey}():$

$s_k \leftarrow Z_q$
$P_k := s_kG$
$D_k := H_q(1||s_k)G$

$\operatorname{Sign}(s_k, B):$

$m = H_q(2||s_k||B)$, $M = mG$
$c = H_q(P_k||M||B)$
$p = m+c*s_k$
$\sigma = (M, p)$

$\operatorname{Verify}(P_k, B, \sigma):$

$c = H_q(P_k || M || B)$
Check if $M+cP_k = pG$

So far, this is a variation of the Schnorr signature scheme which uses the hash-function to generate the private masking key, like it's done in EdDSA instead of randomly picking one. Please note that I highly discourage anyone from using this scheme already since it hasn't gone through formal research.

Based one the rationale that this masking key private, we can use it to create a derivation key to $D_k$.

$\operatorname{GenX}(s_k, B):$

$x = H_q(1||s_k)-H_q(2||s_k||B)$

$\operatorname{DeriveD_k}(\sigma, x):$

$D_k = M + xG$

Let's discuss the properties of this scheme:

Obviously, there is an $X_i$ for each $B_i$ which can be computed easily if you know $s_k$.
Also, each $(\sigma, x)$ tuple should lead to the same $D_k$.
Computing any $\sigma$ should require $s_k$. Calculating $x$ from any $\sigma$ requires knowledge of $s_k$ as well.
Even if you know $D_k$ and a $\sigma$, finding $x$ is as hard as solving the discrete logarithm of $D_k-M$.
Even if you know $D_k$, and choose a $x \leftarrow Z_q$, you would need to forge a signature.
Let's discuss the privacy of the signer by assuming one would compute the challenge by $H_q(M || B)$ and someone knows $\sigma$. He could then compute $P = c^{-1}(pG - M)$. This is circumvented by incorporating the public key into the challenge.
Given a dishonest signer, he could chose a random $y \leftarrow Z_q$ and use it as private key for $D_k$ instead of $H_q(1||s_k)$ or could create commitments which do not lead to $D_k$.

Again, I do not recommend using this scheme since it has not undergone any research at all instead of my two hours.


Is it safe to publicly expose PBE-protected PGP secret keys? I am working on a PGP scheme where a private key is created offline (and in volatile memory) and must be reused on very rare occasions to sign a piece of exportable data.  The private key is locked using a random passphrase with ~256 bits of entropy, and the passphrase and resultant PGP secret key are written on paper and locked up for later use.  The key needs to remain usable for years in the future.

To simplify the future import procedure by reducing the amount of manually entered data, would it be safe to publicly export the secret key file provided the passphrase is kept locked up?  That way, the secret key can be imported off of a flash drive or similar, while only the passphrase needs to be keyed in.

What I understand from the question, as if you have a Certificate Authority key around.

Using an air-gapped pc, raspberry pi zero, etc. is a good choice. The important points;

Sign the document in the offline solution, do not carry the key.
You can have more than one air-gapped solution. Extra hardware against failures.
You can keep your old paper around.
Have an extra security against the easy copying from the device

Extream care

Off-line encryption: In the military, when a message is top secret, the message, firstly, encrypted with an off-line system that has no connection to the network. After the off-line encryption, the message is sent by on-line crypto. The problem is not finished here.

Tempest Attack: The signal from a pc can be carried by air or the power lines. This requires an expert in this area to filter the machine. So the off-line system and the power lines are filtered.

Covert channel: If an adversary can install a software to your air gapped solution that he can use the heat to transfer the data. Have a mechanism to prevent access to the solution.


Why is the second XOR operation in OCB mode necessary? In Rogaway's OCB mode, the offset (derived from the key) ist XOR-added twice: Once to the plaintext block, and a second time after the Encryption.

I am wondering, why the second XOR operation is necessary. The design is  I believe inspired by the XEX construction introduced by DESX. In that case, the second XOR is needed to prevent a meet-in.the middle-attack, but that's not really a problem for OCB.

I am wondering, why the second XOR operation is necessary.

If it is omitted, then an arbitrary permutation of the ciphertext blocks would not modify the tag, and hence any such modification would not be detected.

In the decrypt direction, the checksum (which is what the tag depends on) is an xor of all the values generated by the AES block decryption xored with a key/nonce dependent constant (which is the xor of all the delta's, but that's not important).  If you permute the ciphertext blocks, then you would perform the block decryptions (which would result in the same intermediate plaintexts, just in a different order); they would xor to the same value (xor'ed with the same key/nonce dependent constant), and so the checksum is not modified, and hence the tag is not modified.

The second XOR operations prevents this; with that second XOR, a permutation of the ciphertext blocks would alter the list of internal ciphertext blocks presented to AES (in the decrypt direction), and so alter the list of internal plaintext blocks generated by AES.

  The design is I believe inspired by the XEX construction introduced by DESX.

Nope; Phil Rogaway had a concrete reason for doing what he designed...


constructing QR-like one way function I am wondering whether the following form is a one way function with collision resistance:
$$ax^2+by^2 \mod p$$
where $a$ and $b$ are given, and $p$ is a prime number.

Since the QR (quadratic residue) $x^2 \mod p$ is one way, $ax^2 \mod p$ is also one way.
The same goes for $by^2$.

So, my guess is that the form $ax^2+by^2 \mod p$ is one way. Is that correct?

A few more follow-up questions:

How to formalize a proof that a numeric equation is one way?
Does anyone know an archive collecting all of known one way functions?
If $ax^2+by^2 \mod p$ is not one way, how about $a^2x+b^2y \mod p$?
What is instead of a prime $p$ we have a composite number (possibly with certain assumptions on its factorization)?

From your comment, I replace $p$ with a composite $n$.
The answer is no.

The problem is determining whether $f(x,y) = a x^2 + b y^2 \bmod{n}$ is one-way or not.
We want to find $(x',y')$ such that $f(x',y') = z$, given $a, b, n$ and $z = a x^2 + b y^2 \bmod{n}$.

Let us consdier $f'(x,y) = x^2 + h y^2 \bmod{n}$, where $h = b a^{-1} \bmod{n}$.
The problem is now finding $(x',y')$ satisfying $f'(x',y') = m$, given $m = z a^{-1} \bmod{n}$, $h = b a^{-1} \bmod{n}$, and $n$.

The problem is a basis of the Ong-Schnorr-Shamir signature (STOC 1984, CRYPTO 1984).
We already know that Pollad and Schnorr (1987) cryptanalyzed this scheme without factoring $n$.
The algorithm and example is available in a short note written by Jeffrey Shallit.


SSL-like protocol with public-key hard-coded in the client Imagine a SSL-like protocol that instead of using certificates signed by a trusted CA, has the server's public key hard-coded in the client.
My question is: what happens if the server's private key is compromised?
Without certificates, the system doesn't have a CRL (Certificate Revocation List) and until the users update the client, the attacker can impersonate the server. How can one build a system that makes public-key revocation possible while having the public-key hard coded in the client?

If the application completely trusts the public key (e.g., runs code signed by it), then you could add "master key change" messages that can be signed by it, that make the application change it's hard-coded key. For additional security, you could require that the new key be additionally signed by a key hopefully separated from the now-compromised one - here decent options are either an additional more-secured key or confirming the new master key via HTTPS (trusting the CA hierarchy).

Of course in all methods you must ensure the client gets reasonably recent revocation messages - which may require periodic signing of "non-revocation" messages - but note that CRLs have this problem too.


Pseudorandom number generator for which it is impossible to deduce the seed I'm looking for an RNG that in the case that an attacker would get all or part (most likely part) of the pseudorandom data, there will be no way for them to deduce the original seed more efficiently than brute force.

Which RNG's would comply with my requirements?

Random number generation is the generation of a sequence of numbers or
  symbols that cannot be reasonably predicted better than by a random
  chance... Source: Wikipedia

It follows that "an attacker [with] all or part" of the sequence cannot "predict any non-given [part of the sequence] better than guessing," as hinted in a comment, so guessing is the best an adversary can do.

The original question mentions pseudorandom data and an original seed, without relation to RNGs, so perhaps the question is missing something and I'm answering the wrong question.


What are "unspecified" differentials in a differential characteristic? I've been studying many papers on differential cryptanalysis and I see that in the published differential characteristics, such as in the appendices of [1], [2] and [3], some differences are left "unspecified" (usually denoted by ** or -).
Why are these differences left unspecified? Since the differentials pass through an S-box, shouldn't their probability be counted? Additionally, how to determine which differentials can be left unspecified and which cannot? Specifically, I'm asking in the context of boomerang attacks
For a more concrete example, section 3.2 from this paper [1] lists a toy example of computing the probability of a differential characteristic for SKINNY:

Example 1. Figure 3 shows a toy example of boomerang characteristic
with two differential characteristics on 3 rounds of SKINNY-64(the upper
characteristic is above the lower characteristic). We suppose that we
are not adding differences in the key (SK model), so we omit the key
from the figure as it will not modify the differences. Lime (for the
upper characteristic) and pink (for the lower characteristic) colored
cells are non zero differences,and grey cells are unspecified
differences. All the differences are given in hexadecimal. We denote
the input and output differences by ∆ex=
[0,d,d,0,0,0,0,0,0,5,0,0,0,0,0,0] and ∇ex=
[0,0,2,0,0,2,0,0,0,0,0,0,0,0,0,0] respectively.

In R1 of the upper characteristic, the cell in position 1 (starting from top left, from left to right) with value "2" passes through the SB layer to the "unspecified" gray cell, thus its probability is not counted. It's not clear to me why these cells in particular do not have their probabilities counted in the total prob. of the distinguisher, and why some cells are seemingly more important than others.

In these papers they are trying to search for a strong boomerang trail and are semi-exhaustively searching over families of trails where each family has a higher chance of holding than a trail chosen uniformly at random from all possible trails. In these families the unspecified differentials are what we (semi-)exhaust over and the specified parts of the differential are fixed for the family and improve the probability of a typical member of the family above uniform random.
In your example we are looking at two families of differential trails (one upper and one lower) where the fixed differentials for the upper family are lime and white and the fixed differentials for the lower family are pink and white. The fixed parts of the differentials were likely chosen because they have a very high probability of holding and the maximum probability of differentials on the unspecified parts was not as strong. Greedily choosing likely values of the grey differentials gives a large collection of high probability trails for both the upper and lower families. These can then be efficiently pairwise tested using a meet-in-the-middle approach to calculate the probability of the trails combining to make a strong boomerang trail using e.g. a Boomerang Connectivity Table. Trying enough upper and lower trails will hopefully result in a high probability upper trail that combines well with high probability lower trail and a very strong overall boomerang distinguisher.
Note that if more than one strong trail is found, the probabilities reinforce as the same statistical test will detect any trail that has the same start and end points.


Montgomery Reduction - Conditions on R In Montgomery Reduction, we need to compute $z = x y \text{ mod  } N$ and the Montgomery Reduction of $x$ is $xR^{-1}$.

Why should the choice of $R$ be $2^l$ where $l$ is the length of $N$ to the base $2$?
Why cannot we have a larger $R$?

This is a cross question with math.stackexchange.

First of all, The Montgomery's Reduction algorithm requires that $\operatorname{GCD}(n,R)=1$ .
This requirement is satisfied iff $n$ is odd.

The $R$ is chosen as $2^l$ where $ 2^{l-1} \leq n < 2^{l}$.

For $x < n$  the $n$-residue with respect to $R$ is defined as;

$$ x' = x \cdot r \bmod n$$ than the set

$$\{i \cdot R \bmod n\;|\; 0 \leq i \leq n-1 \}$$ is a complete residue system, that is, it contains all the numbers between $0$ and $n-1$.

The selection of $R$ is the smallest bound.

  Why should the choice of $R$ be $2^l$ where $l$ is the length of $N$ to the base $2$?

Montgomery Reduction converts arbitrary division into shift operations. Therefore  $2^l$  is a good choice for computers, we have to shift $l$ bits.

  Why cannot we have a larger $R$?

It won't be effective since you will have more unnecessary shiftings due to a larger $R$.

note: if $R<n$ than this will not work.


Can we use a PRF as a PRP? Leaving aside the problem of how to compute the inverse of a PRF F, may we use it also as a PRP?

The reciprocal of this statement is true, see for instance Katz and Lindell, Proposition 3.27, when the input length of F is sufficiently large. However, in practice to build a PRP from a PRF people use a Feistel network. This would address the problem of making the PRF invertible.

Leaving aside the invertibility I guess the same proof for PRP $\implies$ PRF is useful here. Am I right?

If the output domain is large enough so that the probability of getting a collision in the PRF is negligible, then the output of a PRP and PRF are indistinguishable. Thus, in principle, the answer is yes - you can interchange these freely (under the above condition).

Having said that, it's unclear to me why you would want a non-invertible PRP rather than a PRF. Typically, a PRF is better for cryptographic constructions, being easier to analyze and giving better bounds, and the only time we use a PRP is when we want to invert. Maybe there is an example of a use of a PRP specifically when inversion is not needed, but I don't think I've ever seen one (and can't really think of where it would be helpful).


SHA-256 Hashing Functionality It seems all these options are correct to me

  fingerprint of the provided input.
  A one-way deterministic hash function.
  symmetric hash function
  A hash function that generates a digest.

Anyone identify the wrong option and why?

"A has that generates digest" seems wrong because a hash can not do much. You need a function to make something.
"A one-way deterministic hash function" is correct. In theoretic computer engineering, it is not known whether "one-way"-functions really exist. But in common sense hash is called a "one-way"-function. And they are deterministic. For the same input, you get the same output.
"symmetric hash function" is correct. Hash algorithms are part of symmetric cryptography.
"a hash function that generates a digest" is correct. See 1.


RSA exercises example I have doubts about this question

  Consider the following textbook RSA example. Let be p = 7, q = 11 and
  e = 3. Give a general algorithm for calculating d and run such
  algorithm with the above inputs.  What is the max integer that can be
  encrypted? Is there any changes in the answers, if we swap the values
  of p and q?

I tried to apply RSA in this way:

$p=7$ and $q = 11$ so $n=(pq)$ and $n=77$, therefore $$\phi(pq) = (p-1)(q-1) = (7-1)(11-1)= 60$$

Pick $e$ that is $<60$ and isn't coprime (which means I can't use $2,3$ and $5$)

So after that, I'm blocked, and my solution is to choose another coprime, for example $e=7$ in order to have  public-key: $(n,e)= (77,7)$

But I'm wrong somewhere, because if I use $7$ (or another coprime like $11$) I can't compute $d$.
In fact, for all numbers that I used, for example with $e=7$, if I pick $d=9$ I have $63$ that if I divided for $60$ I have $1$ with rest $3$.

So my questions are these :

Am I wronging? (where?)
As a request , can I pick 3, even if it isn't coprime? (because as I saw
on theory, I need at least a coprime).
pick $e= p$ or $q$ seams wrong.right?

if I use $e=7$ (or another coprime like $11$) I can't compute $d$

You can use $e=7$. When $n$ is squarefree, a private exponent $d$ will work if (not: only if) $e\;d\equiv1\pmod{\phi(n)}$, that is by definition when $e\;d-1$ is divisible by $\phi(n)$. There are solutions to that if and only if $e$ is coprime with $\phi(n)$. The textbook systematic way to find such $d$ is the Extended Euclidean Algorithm. See there for a more efficient and easier to implement variant; or there for a "binary" variant.

Note: When $n$ is squarefree, the necessary and sufficient condition for $d$ to work in RSA is: $e\;d\equiv1\pmod{\lambda(n)}$ (where $\lambda$ is the Carmichael function). That simplifies computation of $d$, and typically leads to a smaller one. $d=e^{-1}\bmod\lambda(n)$ is required by some RSA standards including FIPS 186-4. When $n$ is the product of distinct primes $p$ and $q$, $\lambda(n)$ can be computed as
$$\begin{align}\lambda(n)&=\operatorname{lcm}(p-1,q-1)\\&=\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}\end{align}$$

  Can I pick $e=3$, even if it isn't coprime with $\phi(n)$?

No. It is required that $e$ is coprime with $\phi(n)$ [equivalently: that $\gcd(e,p-1)=1=\gcd(e,q-1)$ ] in order to insure unique decryption of ciphertexts. Otherwise, there will be multiple plaintexts $m\in[0,n)$ leading to the same ciphertext $m^e\bmod n$. In your case $(n,e)=(77,3)$, for example, $m=4$ and $m=15$ would lead to the same ciphertext $64$.

  Picking $e=p$ or $q$ seams wrong

For large $n$, it would be bad to choose $e$ equal to a factor of $n$ (or with any other approximate relation between $e$ and a factor of $n$) since that would allow factoring $n$. But when one deliberately illustrates RSA with a toy $n$ such as $n=77$ which is trivial to factor, choosing $e$ equal to one of the factors is a non-issue. Still, one could use $e=13$ to avoid that special case.

  What is the largest integer that can be encrypted?

In textbook RSA, plaintext and ciphertext space is the integer interval $[0,n)$. The largest integer that can be encrypted (and decrypts correctly) is thus $n-1$. Notice that it is always encrypted to itself, thus trivial to decipher. More generally, textbook RSA is insecure when directly used to encipher data. It is conjectured secure when $p$ and $q$ are large random secret primes, and a random $x$ in the plaintext space $[0,n)$ is enciphered.


Build set with PKI from reliable broadcast / random beacon I am trying to build a protocol (or find an existing one) for creating a set $S_2$ with PKI from a set of parties $S_1$ that initially does not know anything about the other parties.

We assume end-to-end communication and broadcast, all with a delay up to $\text{Delta}_\text{transmission}$. Additionally, we also use NIST random beacon (could simplify the protocol, but it doesn't solve the deadline problem below).

So every party $p \in S_1$ would run this protocol $A$ at a time $t_1$, and we would like at $t_2$ that all honest parties have the same set $S_2$ of parties with PKI.

I could imagine a solution where all parties generate a private/public key pair, and then the protocol dictates that for each round, they broadcast a signed message with their public key and current vision of $S_2$; ie $m = [pk, S_2]$.

each time they receive a valid signed message with a new public key $pk'$ and a new set $S_2'$, they do $S_2 = S_2' \cup S_2 \cup {pk'}$, and rebroadcast $[pk, S_2]$

The main problem with this scenario is termination : if we want the protocol to terminate at any deadline $t_2$ fixed in advance; there is always a way for an attacker to break consistency (all honest parties have the same set $S_2$ in the end) by sending a new valid message $m'$ just before the deadline to a party $p$, so that this party accept it, but when the honest party rebroadcasts his new set including the new key, other honest parties discard it because it arrives after the deadline $t_2$.

Any help, either directly on how to fix the deadline problem, or indirectly how to build such protocol, would be greatly appreciated :)

There might be multiple solutions, and this could be one of them.

You can use multiple rounds of Terminating Reliable Broadcast (TRB). Each party in $S_1$ sends a message with their own proposal $pk$ -- this corresponds to one round of TRB.

After $|S_1|$ rounds, you're good to go. Since all honest parties have the same set of individual proposals, they can deterministically compute the result $S_2$.

Naturally, if you assume $f<|S_1|$ nodes can fail (e.g. by crashing, arbitrary), you have to stop the protocol after $|S_1|-f$ rounds.

PS: I might have misunderstood some of the details in your the question, so please correct me if anything's amiss.


Why does SHA-1 rotate the variables A and B? SHA-1 has an operation within round j in stage t, where the functions $f_t$ and $K_t$ change depending on the stage.

Is there a specific reason why the variable $A$ is rotated by 5? How does this improve security? And why not rotate the variable by 30 like $B$ is?

I have the same question about $B$: why is the variable rotated and why isn't it rotated by a different amount?

Most the other operations you see in the round – XORs and $f_t$ – are bitwise functions. Without rotations every bit would only affect the corresponding bits in the other words and the higher bits in some words due to carry propagation. That means the low order bit would be affected by only the low order bits of the inputs $W_j$ and $K_t$, allowing simple inversion in the case of SHA-0 (where $W_j$ themselves are straight up combinations of input words) and significantly weaken SHA-1 (where $W_j$ are rotated).

So you need some rotations – or other operations like right shifts – to allow bits at different positions to mix completely.

The particular numbers (rotation constants) are not quite as important, but 5 and 30 are are different enough and not large factors of the word size (e.g. consider 16). There are some possibly better ones (pdf), but 5 and 30 (= -2) are also small, which at least used to matter in some low performance computational units.


What is the intuition for ECDSA? I understand DH and ElGamal and RSA encryption/signatures.  But when I look at ECDSA (or plain DSA), it seems like the formulas are just pulled out of thin air.  I can verify that the algebra used in the verification formula does in fact work out, but I have no clue why forgeries are hard, why these formulas were used, why something simpler wouldn't work, and where the inventor(s) got all this stuff.  Can someone explain the intuition behind ECDSA?

It is possible to view DSA/ECDSA as an identification scheme (like Schnorr) but with a different variant of Fiat-Shamir. This gives the intuition that you are perhaps looking for. I will include an excerpt from Intro to Modern Cryptography 2nd edition (Section 12.5.2) which gives this explanation:

Begin Excerpt -- Section 12.5.2 DSA and ECDSA

The Digital Signature Algorithm (DSA)
and Elliptic Curve Digital Signature Algorithm
(ECDSA) are based on the discrete-logarithm problem in different
classes of groups.
They have been around in some form since 1991, and
are both included in the current Digital Signature Standard (DSS)
issued by NIST.

Both schemes follow a common template and can be viewed as being constructed
from an underlying identification scheme
(see the previous section).
Let $ \mathbb{G}$ be a cyclic group of prime order $q$ with generator $g$.
Consider
the following identification scheme in which the prover's
private key is $x$ and public key is $( \mathbb{G}, q, g, y)$ with $y=g^x$:

The prover chooses uniform $k \in \mathbb{Z}_{q}^*$ and sends
$I:=g^k$.
The verifier chooses and sends uniform $\alpha, r \in \mathbb{Z}_{q}$ as the
challenge.
The prover sends $s:=[k^{-1} \cdot (\alpha+xr) \bmod q]$ as the
response.
The verifier accepts if $s\neq 0$ and $g^{\alpha s^{-1}} \!\cdot
    y^{r s^{-1}}=I$.

Note $s \neq 0$ unless $\alpha=-xr \bmod q$, which occurs with negligible
probability. Assuming $s \neq 0$, the inverse $s^{-1} \bmod q$ exists and
$$
g^{\alpha s^{-1}} \! \cdot y^{r s^{-1}}
 = g^{\alpha s^{-1}} \! \cdot g^{xrs^{-1}}
  = g^{(\alpha+xr) \cdot s^{-1}}
   = g^{(\alpha+xr) \cdot k \cdot (\alpha+xr)^{-1}} = I.
$$
We thus see that correctness holds with all but negligible probability.

One can show that this identification scheme is secure if the discrete-logarithm
problem is hard in the group. We merely sketch the argument, assuming
familiarity with the results of the previous section (i.e., Schnorr and identification schemes).
First of all, transcripts of honest executions can be simulated:
to do so, simply choose uniform $\alpha, r \in \mathbb{Z}_{q}$
and $s \in \mathbb{Z}_{q}^*$, and then set $I:=g^{\alpha s^{-1}} \!\cdot y^{r s^{-1}}$.
(This no longer gives a perfect simulation, but it is close enough.)
Moreover, if an attacker outputs an initial message $I$ for which it can give
correct responses $s_1, s_2 \in \mathbb{Z}_{q}^*$ to distinct challenges $(\alpha, r_1),
(\alpha, r_2)$ then
$$
g^{\alpha s_1^{-1}} \!\cdot y^{r_1 s_1^{-1}} = I = g^{\alpha s_2^{-1}} \!\cdot y^{r_2 s_2^{-1}},
$$
and so $g^{\alpha (s_1^{-1} - s_2^{-1})} = h^{r_1s_1^{-1} - r_2s_2^{-1}}$ and
$\log_g h$ can be computed as in the previous section. The same holds if the attacker
gives correct responses to
distinct challenges $(\alpha_1, r), (\alpha_2, r)$.

The DSA/ECDSA signature schemes are constructed by ``collapsing'' the above identification
scheme into a non-interactive algorithm run by the signer. In contrast
to the Fiat--Shamir transform, however, the transformation here is carried out
as follows:

Set $\alpha:=H(m)$, where $m$ is the message being signed and $H$ is
a cryptographic hash function.
Set $r:=F(I)$ for a (specified) function $F: \mathbb{G}\rightarrow
   \mathbb{Z}_{q}$. Here, $F$ is a ``simple'' function that is not
intended to  act like a random oracle.

The function $F$ depends on the group $ \mathbb{G}$, which in turn depends on the scheme.
In DSA,
$ \mathbb{G}$ is taken to be an order-$q$ subgroup of $\mathbb{Z}_{p}^*$, for $p$ prime, and
$F(I) =[I \bmod q]$.
In ECDSA, $ \mathbb{G}$ is an order-$q$ subgroup of
an elliptic-curve group $E({\mathbb Z}_p)$, for $p$ prime. (ECDSA also allows elliptic curves
over other fields.)
Any element of such a group can be represented as a pair
$(x, y) \in {\mathbb Z}_p \times {\mathbb Z}_p$. The function $F$
in this case is defined as $F((x,y)) = [x \bmod q]$.

DSA and ECDSA - abstractly:
Let $\cal G$ be a group -generator algorithm.

$\sf gen$: on input $1^n$, run ${\cal G}(1^n)$ to obtain $( \mathbb{G},
   q, g)$. Choose uniform $x \in \mathbb{Z}_{q}$ and set $y:=g^x$. The
public key is $(\mathbb{G}, q, g, y)$ and the private key is
$x$.

As part of key generation, two functions $H: \{0,1\}^* \rightarrow
   \mathbb{Z}_{q}$ and $F:  \mathbb{G}\rightarrow \mathbb{Z}_{q}$ are
specified, but we leave this implicit.
$\sf sign$: on input the private key $x$ and a message $m \in
   \{0,1\}^*$, choose uniform $k \in \mathbb{Z}_{q}^*$ and set
$r:=F(g^k)$. Then compute $s:= [k^{-1} \cdot (H(m) + xr) \bmod q]$.
(If $r=0$ or $s=0$ then start again with a fresh choice of $k$.)
Output the signature \mbox{$(r, s)$}.
$\sf vrfy$: on input a public key $(\mathbb{G}, q, g, y)$, a message
$m \in \{0,1\}^*$, and a signature $(r,s)$ with $r, s \neq 0 \bmod
   q$,  output 1 if  and only if  $$ r = F\left(g^{H(m) \cdot s^{-1}}
   y^{r \cdot s^{-1}}\right). $$

Assuming hardness of the discrete-logarithm problem,
DSA and ECDSA can be proven secure if $H$ and $F$ are modeled as random oracles.
As we have discussed above, however,
while the random-oracle model may be reasonable for $H$,
it is not an appropriate model for $F$. No proofs of security are known for the specific
choices of $F$ in the standard. Nevertheless, DSA and ECDSA
have been used and studied for decades without any attacks being found.

Proper generation of $k$.
The DSA/ECDSA schemes specify that the signer should choose a uniform $k \in \mathbb{Z}_{q}^*$
when computing a signature. Failure to choose $k$ properly (e.g., due
to poor random-number generation) can lead to catastrophic results.
For starters, if an attacker can predict the value of $k$ used to compute a
signature $(r, s)$ on a message $m$, then they can compute the signer's private key.
This is true because
$s = k^{-1} \cdot (H(m)+xr) \bmod q$, and if $k$ is known then the only unknown is the
private key $x$.

Even if $k$ is unpredictable, the attacker can compute the signer's private key
if the same $k$ is ever used to generate two different signatures. The
attacker can easily tell when this happens because then $r$ repeats as well.
Say $(r, s_1)$ and $(r, s_2)$ are signatures
on messages $m_1$ and $m_2$,
respectively. Then
\begin{eqnarray*}
s_1 & = & k^{-1} \cdot (H(m_1)+ x r) \bmod q \\
s_2 & = & k^{-1} \cdot (H(m_2) + x r) \bmod q.
\end{eqnarray*}
Subtracting gives $s_1-s_2 = k^{-1} \left(H(m_1)-H(m_2)\right) \bmod q$, from which $k$
can be computed; given $k$, the attacker can determine the private key $x$ as
in the previous paragraph.
This very attack was used by hackers to extract the master private key
from the Sony PlayStation (PS3) in 2010.


hash function for elliptic curve co-ordinates Is there any hash function which takes the co-ordinates of an elliptic curve $E_p(a,b)$ as input and gives an integer value i.e.

$h(.) : \{(x,y) \in E_p(a,b)\} \rightarrow \mathbb{Z}$

Let $k$ denote the bit-size of $p$.  Let also a hash function $H \colon \{0,1\}^{2k} \to \{0,1\}^\ell$.  We define the hash value of a point $P = (x,y)$ on an elliptic curve over $\mathbb{F}_p$ as
$$h \colon E_p(a,b) \to \mathbb{Z}, (x,y) \mapsto H(x + 2^k y)$$

One-wayness follows from hash function $H$ (for example SHA-3).

Note. There is a slight abuse of notation above, integer $x+2^ky$ should be seen as a binary string when applying hash function $H$; and the output (namely, $H(x + 2^k y)$) should be regarded as an integer.  This is done by the canonical representation: a $t$-bit integer $a \in \mathbb{Z}$ can uniquely be represented as $a = \sum_{i=0}^{t-1} a_i 2^i$ with $a_i \in \{0,1\}$, which in turn can be seen as the $t$-bit binary string $a_{t-1}a_{t-2}\ldots a_0$, and conversely.


Are there any signature schemes for underpowered devices (8-bit microcontroller)? I am currently researching into a small scale home automation system, aiming for cost. The system architecture is basically one master and several slaves which are connected in parallel.

Recently i've bumped into the natural question of system security. I'm mainly concerned with authentication, that is, I need the slave to be able to tell if a command issued is really trustable. In other words, verify that some command was really sent by the master, and not some impersonator which has connected to the communication bus.

I've started researching and found out about several implementations directed towards low end microcontrollers, including elliptic curve cryptography.

That is all very fine indeed, but I am only worried about signing in a public key scheme. I don't need to do actual data encryption and decryption.

I am aiming for really low cost, so the space available for code is rather small.

I accept all kinds of suggestions, but here comes my real question:

Would it be unsafe to use a scheme like Rabin signature in an awkward way like this:

Use a very small-sized key - 160 bits
Generate a new set of keys and send the public key to the slaves often, so even if it takes a relatively small amount of time to factor the public key, the attack is impractical because it has already changed when the attacker is ready

Mind that this is mostly a theoretical experiment - my aim is only to gain knowledge into cryptography on small devices. Also, this safety would be merely an extra layer on my system and not critical. As I only need signing and verification and not en/decryption I can do without a lot of code dedicated to this. The master is a PC, so the key generation is easy. The slaves do NOT need to authenticate themselves to the master.

Also, note that the signing is to be made on a small block of data which would be sent along with the main command message. This block, when parsed correctly guarantees the identity of the master. As for sending a new key to the slaves, it too would be accompanied by a block which has to be parsed correctly by the old key, or else an attacker could overtake the communication bus.

Update:

Hardware specs

The target platform is for now the S08 family of Freescale's 8bit MCU line. The most likely candidate in this section, considering the low cost would be a MCU with 32K/2K FLASH/RAM. The CPU can reach a maximum operating frequency of 40MHz. Anything under one second for verification is fairly acceptable.

I also have access to a 128K/8K MCU of the same family. However, as a learning exercise I am trying to cut down everything that is possible and be able to get the same code to run on a scaled down version of this MCUs which is cheaper: 8K/768B FLASH/RAM.

In my tests, even the ultra-low spec one is able to run the verification of a 320bit Rabin-signed block. Of course I could throw away the low-spec parts and concentrate on the bigger ones, but this is to be really a learning experiment and I would like to push the boundaries as far as they can go.

Final Update

For those interested, my chosen solution is to abandon authentication for really small sized devices. These will be able to connect to the bus but are insecure, and so must not take part in tasks which are critical. The slaves which must support the authentication process will be built upon MCUs with some more RAM to support the 1536-bit or greater key suggested. Most likely the Rabin cryptosystem will be used for its simpler maths. As before, only authentication is interesting at this moment.

For your application: "I need the (underpowered 8-bit) slave to be able to tell if a command issued is really trustable", RSA signature with low public exponent ($e=3$), or Rabin (an analog with $e=2$), is likely the most appropriate, assuming you can't trust the slaves to keep a key secret, which is the only realistic assumption unless that slave uses hardware with a level of physical security comparable to a Smart Card, like this 8-bit IC (link to TOE).

For example, a standard 8051 core running @4MIPS peak (48MHz xtal) or a 68HC11 @6MHz EClock (24MHz xtal) can verify a 1536-bit RSA signature ($e=3$) per PKCS#1 or ISO/IEC 9796-2 in 1 second, or about half that for Rabin ($e=2$), with well under 4kB of code, and little RAM. There are even faster Rabin-like schemes (though less common).

One problem is size of the signature: it is the same as the modulus, that is in my example 1536 bits (192 bytes) for PKCS#1, but the overhead can be much less with ISO/IEC 9796-2: max(34, 192-M) bytes where M is the size in bytes of the message/command, using a 256-bit hash like SHA-256, thanks to message recovery.

Update: Do not use Rabin with 160-bit public modulus, this is entirely unsafe, see this; such a modulus can be factored in seconds with public-domain tools like GMP-ECM, or perhaps even (with more time) an applet.

Update 2: The 8051 code quoted above uses a minor variation of straight textbook modular arithmetic, without Montgomery (which does not help for modular squaring or cube, at least in standard RSA/Rabin schemes) or Karatsuba, but with extensive low-level optimization in assembly. The variation (relatively straightforward but unpublished AFAIK) is that modular reduction occurs during the multiplication, rather than after, and within the same scanning of intermediary result. It works with no restriction on the modulus bit size or value. That has been used in a commercial implementation, developed and sold over a decade ago for POST of several brands and CPUs, and was (perhaps: is still) used for verification of Smart Card certificates, and/or signed code update. There was strong code size constraints, thus things are not optimized to the max for speed (no loop unrolling), rather for a balance of simplicity and reliability, size and speed. Here is an old commercial doc in French (full disclosure: this is my code & company). If you can make a few reasonable constraints on the public modulus, there are other optimizations leading to further simplification, and moderate speedup.

Update 3: 320-bit RSA modulus was already considered marginally safe 25 years ago, and I wildly guess would be factorisable in minutes on a single modern machine with a good MPQS or SIQS implementation like SIMPQS, or msieve if you find a wizard to get it running. And even with more decent RSA modulus size like 640-bit, the idea of short-lived public keys is hard to get right, especially if the devices must survive power loss. Unless I err, a trusted long-term key is required (chained certificates of short-term keys will not do). Also, your devices need a trusted source of current time (either internal or external). My advice is: forget about it for something secure; a symmetric MAC (as proposed in another answer) might be preferable.

Update 4, revisited: Your S08 CPU has 8x8->16-bit multiplication in 5 cycles. Unless I missed a divisor somewhere, that seems to be 125ns @40MHz. This is over 13 times faster than 10 cycles @6MHz on the HC11 (of 12 years ago) on which my code does 1536-bit RSA, $e=3$ well under 1 second. Bus cycles are also faster (20MHz vs. 6MHz) and I did not see mention of wait states for internal RAM. Despite the lesser instruction set (no 16-bit registers and addition), I guesstimate that a similar highly-optimized implementation on that S08 thing would check a 1536-bit Rabin signature in 0.2 second, give or take a factor of 2, using under 1kByte 416 or 608 bytes of RAM, depending on if the public key (in a form directly usable for computation) is present in Flash or not; this RAM is needed during signature verification only, and can be shared with other non-concurrent tasks; the 192 bytes of signature are included in this low RAM budget, and could be discounted if the signature is at a fixed address. Again this is in hand-tuned assembly, C compilers easily eat a factor of 10 or worst on multi-precision arithmetic, and keeping the RAM budget low requires some care.

Update 5a: A 1536-bit signature is only 192 bytes; and can, as well as the temporary variables necessary to check it, reside in RAM shared with the rest of the application; that is, the stack (which in any half-decent 8-bit development system I use is not the physical stack, but simulated by static analysis of the call tree). Thus you do not face a difficult RAM size issue using a decent RSA modulus key size in your application.

Update 5b: A "chain of certificates" introducing short-term public keys certified by the previous one would not be secure if the slave has to survive power loss, because the adversary can capture the current public key, cut power, factor that, restore power, and then forge a chain of certificates for fake short-term public keys of known factorization, that will be accepted by the slave, and boom the slave is "pwned". This is even if we assume that the slave has access to a trusted source of date/time, and each certificate carries a date/time of expiration.

Update 5c: The question and comments show a tendency to under-size RSA modulus, under the fallacy: if I can't factor it, surely that's good enough to bother my adversaries. That line of thought is wrong and dangerous, at least until one carefully researched the public state of the art (which, one must assume, any intelligent adversary will use), and has used power comparable to modern adversaries who could distribute factorization work on many (perhaps pwned) computers, and can safely assume none of the adversaries is smart enough to improve the state of the art. The sources quoted by keylength.com go one step further, and want some confidence that conceivable improvements in the state of the art, and true computer power available at a price, are unlikely to cause a break in a parameterizable number of years; that's one of the reason they ask for sizes way above the academic state of the art; and perhaps their known state of the art encompass more than the academic; and they of course have a desire to be on the safe side. I'm borderline prudent when I even discuss 640-bit RSA modulus for very short-term keys: 512-bit keys are routinely factored in days by enthusiasts on a shoestring; again see this here, as well as the true tale of banks using 321-bit keys way longer than reason and advise, in a high visibility/stakes application.


How to attack a general polyalphabetic cipher? I am able to decrypt Vigenere ciphertext using the index of coincidence and chi-squared test.

However, out of interest, how do you go about attacking ciphertext that was encrypted using a mixed alphabet shifted 26 times?

Also, what about a ciphertext that has been encrypted with 26 random alphabets? (so each line in the tableau is random)

Googling seems to bring up the basic Vigenere, but either an example or a link to a more detailed resource would be good.

A general polyalphabetical cipher is just a combination of several general monoalphabetical ciphers, each applied on every $n$-th letter of the message.

So the first thing is to find out what $n$ is (i.e. the key length). For this we can use the index of coincidence just like for Vigenere.

Then we can split the message into $n$ parts (columns), and try to break each of it as an individual monoalphabetic cipher, starting with frequency analysis. (We'll have to correlate information from the individual columns to do bigram frequency analysis, too.)


Factoring two RSA moduli $N_i=p_i\cdot q_i$ knowing that $p_2=p_1+2$? It is given two RSA moduli $N_1$ and $N_2$, known to be of the form $N_i=p_i\cdot q_i$, with $p_i$ and $q_i$ unknown primes, and such that $p_2=p_1+2$. Can we make use of that relation to factor the moduli much more efficiently than if it did not held?

If that helps, add extra assumptions if they are plausible for common RSA moduli, such as:

$p_1<p_2<q_1<q_2$
$p_1\equiv1\pmod 4\;$ so that $p_1$ and $p_2$ differ only by their second lowest-order bit
$2^{(k-1)/2}<p_i<q_i<2^{k/2}$ with $k=1024$

This is a minimal subset of this more general question.

The fancy name for this is factorization with an implicit hint. If the primes are unbalanced, i.e., if $\log_2 p_i > 2 \log_2 q_i$, we know how to factor $n_1$ and $n_2$ quite easily. Let $k$ be the number of bits $p_1$ and $p_2$ differ by (a very small $k$, usually, for $(p, p+2)$); reduce the following lattice

$$
\begin{pmatrix}
2^k & 0 & n_2 \\
0   & 2^k & -n_1
\end{pmatrix}
$$

using LLL or equivalent. The resulting shortest vector will be $(2^k q_1, 2^k q_2, 2q_1q_2)$. This method is described, in much more generality (i.e., in terms of shared $p_i$ bits) in Faugère, Marinier, and Renault (see also May and Ritzenhofen, Sarkar-Maitra, Kurusawa-Ueda, and Nitaj-Ariffin).

Two recent papers make improvements to the above lattice-based method, and Theorem 1 of Lu-Peng-Zhang-Lin seems to imply that implicit factorization with balanced moduli is indeed possible. So the answer to your question would seem to be yes.


Why must we generate the signature before any compression being done at PGP? I have done some research on PGP and I found out there are of two reasons why we must generate the signature before doing any compression. Yet, I am not sure I really understand them both.

One reason states that the message must be compressed first and signed later because if we need to do any future validation, we only  need to store the signature – but what I think is if we do the signature first and compression later, we also need to store the signature and compression value. So it will be same as we do the signature first, followed by the compression. Either way, we also need to store the signature and compression value for future validation.

And then there is the second reason… which I do not understand at all:

  Even if one were willing to generate dynamically a recompressed message for verification, PGP's compression algorithm presents a difficulty. The algorithm is not deterministic; various implementations of the algorithm achieve different tradeoffs in running speed versus compression ratio and, as a result, produce different compressed forms. However, these different compression algorithms are interoperable because any version of the algorithm can correctly decompress the output of any other version. Applying the hash function and signature after compression would constrain all PGP implementations to the same version of the compression algorithm

(This 2nd reason is from William Stalling’s book “Cryptography and Network Security”, 4th edition.)

Can anyone help me understand both reasons (especially the later), and/or can you explain to me why PGP expects us to generate the signature before compressing?

As for the first reason: in the future you probably need the decompressed form of the message. There won't be much you can do with the compressed message. But PGP is application level; you may want to verify that message at any time. Now you may want to verify the signature over that decompressed data without compressing it first. E.g. it's a good use case to allow compression over the network and then store the uncompressed message on disk.

As for the second reason: compression works with heuristics and levels of compression. Those levels are hints to the system how much work (CPU cycles mostly) it needs to put in to compress data. Different implementations may make different choices. The compressed format itself will indicate how the compression took place - otherwise you wouldn't be able to decompress of course. So if you decompress on system 2 (using the stored methodology of system 1) and compress it again (using the heuristics of system 2) you are likely to get a different result. Different outputs will result in different signatures, so it makes more sense to sign the uncompressed plaintext.

Semantically it also makes slightly more sense; you wanted to sign the message, right? Not some special compressed representation of it.

Obviously the compression should be completely loss-less for this to work; one bit wrong in the resulting message or a different order of the plaintext and the signature won't verify.


Does the following linear equation hold in bilinear pairings? Does the following hold in bilinear pairings?
$$e(g^{a_1x_1}g^{a_2x_2},g^{c_1}g^{c_2})=e(g^{x_1+x_2},g^{a_1a_2(c_1+c_2)})$$

Yes, sure, in some cases. In the following I assume that we speak about pairings as used in cryptography.

Lets look at the trivial case, i.e., when your equation reduces to $1_{G_T}=1_{G_T}$ where $1_{G_T}$ is the identity in your target group $G_T$. Then any assignment of your variables that makes at least one input element of each pairing the element $g^0=1_G$ ($1_G$ the identity in your group $G$) makes the equality hold. Note if you have $e(a,g^0)=e(a,1_G)=1_{G_T}$ (Observe that for any $a,b \in G$ you have $e(a, b) = e(a, b\cdot 1_G) = e(a, b) \cdot e(a, 1)$ and thus $e(a, 1)=1_{G_T}$). For instance, as in @Artjom B.s example for the case $x_1=x_2=0$.

For the non-trivial case it is quite easy to see that $a_1=a_2=1$ makes the equation hold.


Can a block cipher be used to encrypt wireless communications? Would it be possible to use a block cipher such as CBC in order to encrypt a wireless communication? For example, could I use CBC-MAC, on each block, for encryption for WiFi?

Yes, you can encrypt wireless communication using a block cipher in a specific mode of operation to provide confidentiality. Transport modes also require integrity and authentication to protect against active attacks such as man-in-the-middle attacks.

CBC is however not a block cipher, and neither is CBC-MAC. CBC is a block cipher mode of operation used to provide confidentiality while CBC-MAC is a message authentication code used to provide integrity and authenticity. These constructs use a block cipher such as AES to provide this kind of functionality.

AES (and DES, 3DES, blowfish, Serpent, threefish etc. etc.) are block ciphers. They need to be used with a mode of operation such as CBC to provide confidentiality of messages; they cannot provide such functionality without a mode of operation. A mode of operation also requires an IV or nonce if the key is ever reused. In transport protocols the keys are usually kept for the duration of a session.

WPA2 may use the CCMP which combines AES in CTR (counter) mode for encryption and AES in CBC-MAC mode for integrity and authentication of messages.

Note that the protection of messages is just part of the protocol. Entity authentication and session key establishment require additional cryptographic primitives (a cryptographic primitive is an algorithm such as AES or RSA that is used within a larger scheme).


How does the frequency work with Vigenère Cipher? So I have an unknown key but with the length of 6. I understand that I calculate my own English letter frequency of my letters. I then compare it with the standard English letter frequency and identify a pattern shape similarity (in regards to a bar chart). I get my first letter for the key, however, how do I proceed with  getting the second letter?
What do I change/do to get my second English letter frequency to compare to the standard English letter frequency?
thanks

So in your cipher text, the characters $c_1, c_7, c_{13}, \ldots, c_{1+6i}, \ldots$
should roughly obey the frequency statistics of a permuted or shifted standard English frequency. In the most standard Viginère, if you know E corresponds to cipher letter F (e.g. because it is (one of) the most frequent letters, the key letter is B and the alphabet has been shifted by $1$, allowing for immediate decryption of all letters in this subtext. The same holds for the characters
for encrypted by second key letter $c_2, c_8, c_{14}, \ldots c_{2+6i}, \ldots$: check the histogram, to see if it looks like a shifted standard alphabet etc. In general, the cipher alphabets per key letter could be totally independent and then it can take quite a bit of hand work (guessing words and extrapolating from that) to completely solve the text, but if the standard alphabets are merely shifted, it's rather easy to determine the key letter.


The utility of elliptic curve cryptography Suppose that the only public key cryptography schemes that we knew were Diffie Hellman, RSA and ElGamal. How much would this set civilization back? Are there important applications of elliptic curve cryptography [specifically] without viable substitutes?

[Edit: I came across this question which gives some information, but I'm looking for more. Specifically, I would like to know how much better elliptic curve cryptography is/(would be) than more classical encryption schemes for the applications where elliptic curve cryptography is superior.

If you are restricted to Diffie-Helman, RSA, and ElGamal, I believe you cannot do pairing based cryptography which has applications to attributed based encryption and identity based encryption. These applications are not used heavily in practice, but could be in the next decade or two.

For more information on speed benefits of ECC, see this question and answers. Based on my own testing comparing the elliptic curve variant of exponential ElGamal (which is additively homomorphic) with Paillier (also additively homomorphic and similar-ish to RSA), the elliptic curve cipher was 2 orders of magnitude faster for both encryption and decryption (with a few realistic assumptions as decrypting exponential ElGamal can be tricky). Thus I believe encryption was something like 100ms on one device for Paillier vs 1ms on EC-ElGamal. Decryption was similar.


GCM mode and the order of AAD and plaintext In GCM mode of encryption, what are the limitations on the mixing of plaintext and AAD (additional authenticated data)?

Must the AAD come before the plaintext? Or could it be after the plaintext instead?
Could there be both a block of AAD before the plaintext, and another block of AAD after the plaintext?
Is it possible for AAD and plaintext to be interleaved in some more complicated way?

To extend Conrado's answer, there are three possible ways you might mean ordering:

The order of things location within memory
The order you present things to the GCM implementation
The order of coefficients within the GHASH polynomial

As Conrado mentioned, it doesn't matter where things appear in memory.

And, the order of coefficents are defined within GCM; change the order, and you're no longer doing GCM.  It might be secure (depending on the details of your new scheme), but it's not GCM

On the other hand, there are tricks that allow you to process things in a different order than how they appear in the polynomial.

For example, you can rearrange the GHASH polynomial to be:

$$(A_a H^a + A_{a-1} H^{a-1} + ... + A_0 H^0) H^{m+3} + \\ (M_m H^m + M_{m-1}H^{m-1} + ... + M_0H^0)H^2 +\\ TH$$

(where the AAD block is $(A_a, A_{a-1}, ..., A_0)$, the message is $(M_m, M_{m-1}, ..., M_0)$ is the message and $T$ is the block containing the AAD and message lengths)

With this formulation, you can process the AAD and the message independently, and combine them at the end.

Standard libraries don't implement this, but it certainly could be done.


64bit nonce in AES-CTR, why not 128? I'm just a bit confused about the nonce/IV in AES-CTR ... it seems the suggested way to go is have a 64bit random nonce, and use the last 64bits as the counter, "starting at 0".

I'm just wondering why not PRNG initialize all 128bits? Still using a 'static' 64bit nonce and still with the least significant 64bits as the counter, but "IV"'d (set to a non-zero value).  Am i missing something?

And in this example (https://tools.ietf.org/html/rfc3686) they clearly have a distinction with 1) a 32bit nonce, 2) a 64bit IV, and 3) a 32bit counter. In essence don't the nonce and IV essentially combine to form just one random use-only-once value? (ie. couldn't they just say "a 96bit nonce"?)

Also can the nonce be stored in plaintext alongside the ciphertext, or is it normally stored in some secured fashion, and if so how?
Thanks

Questions

  I'm just a bit confused about the nonce/IV in AES-CTR ... it seems the suggested way to go is have a 64bit random nonce, and use the last 64bits as the counter, "starting at 0".

No, that's just one way of creating a counter block.

Due to the birthday bound you would have about $2^{16}$ messages to have a chance of $1 \over 2^{48}$ that the nonce repeats. Or $2^{32}$ messages with a chance of $1 \over 2^{32}$. Your message size would be $2^{64}$ blocks.

  I'm just wondering why not PRNG initialize all 128bits? Still using a 'static' 64bit nonce and still with the least significant 64bits as the counter, but "IV"'d (set to a non-zero value). Am i missing something?

You're not missing something, that's just another way of doing things.

But this requires the user to generate 128 bits of randomness, and random numbers may not come that cheap - depending on the random number generator used. It would however be tricky to exactly define how many messages at what size (no known bounds), and you'd have to store the initial counter value to detect an overflow (to regenerate keys go into an error condition).

Your scheme could be useful to send many smaller messages in a system that cannot keep state such as a counter for the nonce.

  And in this example (https://tools.ietf.org/html/rfc3686) they clearly have a distinction with 1) a 32bit nonce, 2) a 64bit IV, and 3) a 32bit counter. In essence don't the nonce and IV essentially combine to form just one random use-only-once value? (ie. couldn't they just say "a 96bit nonce"?)

No, if you look at the definition you see that:

  The encryptor can generate the IV in any manner that ensures uniqueness.
     Common approaches to IV generation include incrementing a counter for
     each packet and linear feedback shift registers (LFSRs).

So the IV in the IPsec protocol is there for a different reason than the nonce, which is just there to prevent precomputation attacks (see below).

The IV does not need to be random, which allows for efficient calculation of the counter and a larger message space of $2^{64}$ messages if a counter is used.

  Also can the nonce be stored in plaintext alongside the ciphertext, or is it normally stored in some secured fashion, and if so how?

The nonce in IPsec is a random nonce, so it must be stored alongside the ciphertext (or at least linked to the ciphertext somehow, keeping it with the ciphertext is the most common method). It can be kept in plaintext and does not need to be secured.

IPsec case study

In the case of IPsec, the example in the question, the full counter block is defined using a specific scheme:

  Each PT block is XORed with a block of the key stream to generate the
     ciphertext, CT.  The AES encryption of each counter block results in
     128 bits of key stream.  The most significant 96 bits of the counter
     block are set to the nonce value, which is 32 bits, followed by the
     per-packet IV value, which is 64 bits.  The least significant 32 bits
     of the counter block are initially set to one.  This counter value is
     incremented by one to generate subsequent counter blocks, each
     resulting in another 128 bits of key stream.  The encryption of n
     plaintext blocks can be summarized as:

 CTRBLK := NONCE || IV || ONE
  FOR i := 1 to n-1 DO
    CT[i] := PT[i] XOR AES(CTRBLK)
    CTRBLK := CTRBLK + 1
  END
  CT[n] := PT[n] XOR TRUNC(AES(CTRBLK))

So IPSec allows $2^{64}$ packets to be encrypted if the sequence number is used for the IV, and it allows $2^{32} - 1$ counter for a maximum packet size of over 68GB (1 GB = 10 ^ 9 bytes). Fresh keys are required to be generated whenever the IPsec is restarted or after the encryption of $2^{64}$  packets. It is important to notice that these sizes are not influenced by the nonce.

The nonce is just there to prevent precomputation attacks against the key. This can be found in the security rationale, chapter 7:

  There are fairly generic precomputation attacks against all block
     cipher modes that allow a meet-in-the-middle attack against the key.
     These attacks require the creation and searching of huge tables of
     ciphertext associated with known plaintext and known keys.  Assuming
     that the memory and processor resources are available for a
     precomputation attack, then the theoretical strength of AES-CTR (and
     any other block cipher mode) is limited to 2^(n/2) bits, where n is
     the number of bits in the key.  The use of long keys is the best
     countermeasure to precomputation attacks.  Therefore, implementations
     that employ 128-bit AES keys should take precautions to make the
     precomputation attacks more difficult.  The unpredictable nonce value
     in the counter block significantly increases the size of the table
     that the attacker must compute to mount a successful attack.

So the IPsec has been defined in such a way that it requires a relatively small amount of randomness.

It provides clear bounds on the number of packets (messages) and packet size.

Finally it allows easy detection of overflow so that implementations can go into an error condition rather than to repeat a nonce, destroying confidentiality of the data in the packets.

Although the inclusion of a nonce to prevent precomputation attacks is probably superfluous (due to the large key sizes offered by AES) it may also offer some protection against implementations for which the generation of the IV is faulty.

Note that the CTR spec of IPsec does have its faults:

The name IV is generally used to indicate the initial counter block within cryptographic API's, which is confusing.
It says that "The same IV and key combination MUST NOT be used more than once.", but it should specify that this is specific to the IPsec packets, not the counter blocks.
It doesn't give any security hints in case the IV is generated by an LFSR (pseudo random value).


How does the verification process associated with this signature scheme work? My cryptology professor asked us to show that while the following signature scheme is conceptually valid, that it is inherently insecure, however, I am not sure how to demonstrate that the associated verification process produces an equality if the signature is valid.

The protocol works as follows given:

A publicly shared prime $p$;
A primitive root of $p$, $a|a<q$
A private key: $x|x<q$; and
A public key: $y=a^x\bmod{q}$
A cryptographic hash function $H=\texttt{SHA1}$

A signature $s$ can be generated for $m$ as follows: first, compute $h = H(m)$; if $\texttt{gcd}(h, q-1) \neq 1$ append $h$ to $m$ and calculate a new hash, and continue the process until $h$ and $q-1$ are relatively prime.

Then, calculate $z|z\cdot h\equiv x\bmod{q-1}$ and return the signature $s = a^{z}$.

In order to verify $s$, a user verifies that $Y=(a^z)^{h}=a^{x}\bmod{q}$.

For example, in order to sign a message $m$, where:

$q=6043$
$a=5$
$x=1098$
$y=485$
$h\leftarrow H(m)=612515367434372930600221767499032307523881412051$
$z\leftarrow z\cdot h\equiv x\bmod{q-1}=8513$
$s\leftarrow a^{z} = 5845$

Given the signature $s$, a user can verify that the signature is correct by verifying that $y=(a^{z})^{h}=a^{x}\bmod{q}$, however, I am not sure how to evaluate

$$(a^{z})^{h}= a^{x}\bmod{q}$$

since $h$ is (relatively) large. I (think) that I need to evaluate the following expression, however, I am not sure if its computationally feasible since:

$$(a^{z})^{h}\rightarrow s^{h}\rightarrow 5845^{612515367434372930600221767499032307523881412051}$$

Meaning that in order to verify the signature, I would have to perform the following calculation:

$$(5^{8513})^{612515367434372930600221767499032307523881412051} = 5^{1098}\bmod{6043}$$

Normally, I would use fast modular exponentiation here, but $h$ is absolutely enormous. For a while, I thought that maybe I misunderstood the protocol and $h$ should be reduced modulo $q$, but, again, maybe I just have an embarrassingly flawed understanding of the protocol?

How do you think I should verify the signature?

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

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

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

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