Block ciphers that have Feistel structures are prone to a class of cache attacks known as differential cache attacks, which monitor power or timing side-channels to reveal the secret key. Differential cache attacks were first demonstrated on the block cipher CLEFIA, which has a type-2 generalized Feistel structure. In this paper we improve the attack methodology by showing that a sophisticated method of choosing plaintexts can result in a considerable reduction in attack complexity. This coupled with other cryptanalytic techniques, when applied to the block cipher SMS4, requires just 210 plaintexts to recover the SMS4 secret key from power traces for a 64 byte cache line. Further, the attack becomes more dangerous for large cache lines. For example, with a 128 byte cache line, only 52 power traces are required. Experimental validation of the complete attack has been done on an Intel Xeon microprocessor. Further we suggest an alteration to the SMS4 algorithm that can counter this attack.