With limited computing and storage resources, many network applications of encryption algorithms require low power devices and fast computing components. CHESS-64 is designed by employing simple key scheduling and Data-Dependent operations (DDO) as main cryptographic components. Hardware performance for Field Programmable Gate Arrays (FPGA) and for Application Specific Integrated Circuits (ASIC) proves that CHESS-64 is a very flexible and powerful new cipher. In this paper, the security of CHESS-64 block cipher under related-key differential cryptanalysis is studied. Based on the differential properties of DDOs, we construct two types of related-key differential characteristics with one-bit difference in the master key. To recover 74 bits key, two key recovery algorithms are proposed based on the two types of related-key differential characteristics, and the corresponding data complexity is about 2^42.9 chosen-plaintexts, computing complexity is about 2^42.9 CHESS-64 encryptions, storage complexity is about 2^26.6 bits of storage resources. To break the cipher, an exhaustive attack is implemented to recover the rest 54 bits key. These works demonstrate an effective and general way to attack DDO-based ciphers.