Code-based cryptographic schemes are promising candidates for post-quantum cryptography since they are fast, require only basic arithmetic, and because their security is well understood. Due to their main drawback of large public key sizes, there have been many proposals on how to reduce the key sizes. Many of these use highly structured matrices which can be stored more efficiently. In this paper, we show how a broad class of such structures can be exploited to increase the time and memory efficiency of a Generalized Birthday Attack (GBA), which is one of the best generic attacks against code-based cryptosystems. For example, this improves the best attack against QD-CFS (with n = 30924) and FSB512 by a factor of 180 and 1984, respectively. In general, for a parity-check matrix of size r*n, the improvement is a factor of r, which is typically in the order of 28 to 212.