The development of Internet supports people to transmit information, such as text, images and other media quickly. However, digital images transmitted over the Internet are very vulnerable to attacks, for examples modification and duplication by unauthorized people. Therefore, cryptography as one of method for data security has been developed. This research proposed a combination of color structure CIELab and key randomization by logistic map from chaos as new cipher in digital image cryptographic applications. Cipher is applied to the encryption and decryption process. Implementation of new cipher in cryptographic digital images application was built with Matlab R2010a. Based on the research that has been done, it was found that combination CIELab and chaos can be applied as a new cipher on the encryption and decryption of digital images for cryptographic applications with processing time less than 1 second. Under possible maximum key range on RGB image by 5,2x 1033, the cipher was sufficiently secure against brute-force attack. Decrypted image has good quality with PSNR greater than 50 dB for digital image formatted in “tiff” and “png”.