In recent days, encryption of satellite imagery has attracted a wide range of researchers since these images contain confidential information. Thereby, it is necessary to preserve the privacy of this data to avoid unauthorized access. Two-fish algorithm is one of the widely used image encryption schemes. However, the main drawback of this scheme lies with the static nature of the S-box. To avoid this issue and to improve the quality of encryption, in this paper, we propose a novel algorithm based on chaotic map to create a dynamic S-box structure. In the proposed Chaotic S-Box-based Two-Fish (CSTF) algorithm, a novel chaotic map with improved Lyapunov exponent and approximate entropy has been proposed. The sequences produced by the proposed chaotic map are used to randomize the values inside the static S-box structure of Two-fish algorithm. This encryption scheme is suitable for the encryption of satellite images. The proposed algorithm is validated in terms of S-box evaluation metrics like nonlinearity, bit independence criteria-nonlinearity (BIC-nonlinearity), strict Avalanche criterion (SAC) and bit independence criteria-strict Avalanche criterion (BIC-SAC). To validate the proposed algorithm in terms of key sensitivity, tests like Unified Average Changing Intensity (UACI), Hamming Distance (HD) and Number of Pixels Change Rate (NPCR) have been performed.