Unbalanced Feistel networks F k which are used to construct invertible pseudo-random permutations from kn bits to kn bits using d pseudo-random functions from n bits to (k − l)n bits, k ≥ 2 are studied. We show a new generalized birthday attack on F k , with d ≤ 3k − 3. With 2(k−1)n chosen plaintexts an adversary can distinguish F k (with d = 3k − 3) from a random permutation with high probability. If d < (3k − 3) then fewer plaintexts are required. We also show that for any F k (with d = 2k), any adversary with m chosen plaintext oracle queries, has probability O(m nk/2(k−1)n ) of distinguishing F k from a random permutation.